The out-of-source error in multi-source cross
validation-type procedures

arXiv:1612.07670v1 [math.ST] 22 Dec 2016

Georgios Afendras and Marianthi Markatou

Abstract A scientific phenomenon under study may often be manifested by data
arising from processes, i.e. sources, that may describe this phenomenon. In this
contex of multi-source data, we define the “out-of-source” error, that is the error
committed when a new observation of unknown source origin is allocated to one of
the sources using a rule that is trained on the known labeled data. We present an unbiased estimator of this error, and discuss its variance. We derive natural and easily
verifiable assumptions under which the consistency of our estimator is guaranteed
for a broad class of loss functions and data distributions. Finally, we evaluate our
theoretical results via a simulation study.

1 Introduction
In many situations data arise not from a single source but from multiple sources,
each of which may have a specific generating process. An example of such a situation is the monitoring and diagnosis of cardiac arrhythmias.
Monitoring devices in cardiac intensive care units use data from electrocardiogram (ECG) channels to automatically diagnose cardiac arrhythmias. However, data
from other sources like arterial pressure, ventilation, etc. are often available, and
each of these sources has a specific data generating process. Other potential data
sources include nuclear medicine tests and echocardiograms. Other examples arise
in natural language processing where labeled data for information extraction or parsing are obtained from a limited set of document types.
Georgios Afendras
Department of Biostatistics and Jacobs School of Medicine and Biomedical Sciences, University
at Buffalo, Buffalo, NY, USA, e-mail: gafendra@buffalo.edu
Marianthi Markatou
Department of Biostatistics and Jacobs School of Medicine and Biomedical Sciences, University
at Buffalo, Buffalo, NY, USA, e-mail: markatou@buffalo.edu

1

2

Afendras and Markatou

Cross validation is a fundamental statistical method used extensively in both,
statistics and machine learning. A fundamental assumption in using cross validation is that the observations are realizations of exchangeable random variables, that
is both, the training and test data come from the same source. However, this is
not necessarily the case when data come from multiple sources. Geras and Sutton
(2013) state that “for data of this nature, a common procedure is to arrange the cross
validation procedure by source”.
In this setting, we are interested in estimating the generalization error of learning
algorithms.
The generalization error is defined as the error an algorithm makes on cases that
the algorithm has never seen before, and is important because it relates to the algorithm’s prediction capabilities on independent data. The literature includes both,
theoretical investigations of risk performance of machine learning algorithms as
well as numerical comparisons.
Estimation of the generalization error can be achieved via the use of resampling
techniques. The process consists of splitting the available data into a learning or
training set and a test set a large number of times and averaging over these repetitions. A very popular resampling technique is cross validation. We are interested
in investigating the use of cross validation in the case of multi-source data, where
testing occurs on elements that may not have been part of the training set on which
the learning algorithm was trained. We do not offer here a detailed overview of cross
validation. The interested reader is referred to Stone (1974, 1977) for foundational
aspects of cross validation, Breiman et al. (1984, Ch.s 3,8), Geisser (1975), and to
Arlot and Celisse (2010) for a comprehensive survey.
Two very popular cross validation procedures are the k-fold cross validation and
the random cross validation. In k-fold cross validation we split the data randomly
in k equal parts. Each of these parts is a test set and the remaining data serves as
a training set. In random cross validation case we split randomly the data into two
sets of sizes n1 and n2 (n = n1 + n2 is the total sample size) that serve as training/test
sets and repeat this process J times.
Carrying out inference on the generalization error requires insight into the variance of the estimator of it. Nadeau and Bengio (2003) provided estimators for the
variance of the random cross validation estimator of the generalization error, while
Bengio and Grandvalet (2004) addressed estimators of variance in k-fold cross validation. Furthermore, Markatou et al. (2005) proposed moment approximation-based
estimators of the same cross validation estimators of the generalization error, and
compared these estimators with those provided by Nadeau and Bengio.
Afendras and Markatou (2016) study the optimality of the data splitting for both,
random and k-fold cross validation procedures establishing the corresponding optimization rules. Their work offers closed form solutions to corresponding optimization problems for a broad and commonly used class of loss functions.
A recent article by Geras and Sutton (2013) addresses a formulation of the outof-source (OOS) error in a multi-source data setting. In their framework there are
k sources. If the data size is n, the sample size of each source is n/k. The observations of each source are independent and identically distributed (iid) realizations

The out-of-source error in multi-source cross validation-type procedures

3

of random variables/vectors from an unknown distribution. The elements that belong to a specific source constitute a test set, while the union of the elements of
the remaining sources constitutes the corresponding training set. Geras and Sutton
(2013) construct their cross validation-type decision rule using the elements of the
aforementioned training set. In this sense, their procedure can be thought of as kfold cross validation with the fundamental difference that the test set data does not
necessarily follow the same distribution as the training data.
Recently, multi-source data analysis has received considerable attention in the
literature. Ben-David et al. (2010) study the performance of classifiers trained on
source data but tested on target data, that is data that do not necessarily follow the
same distribution with the source data. Specifically, they study conditions under
which a classifier performs well, as well as strategies to combine a small amount
of labeled target data at the training step of the classifier to facilitate better performance.
This paper is organized as follows. Section 2 presents a motivation of the problems studied here, while Section 3 establishes the framework and notation that is
used in this article. Section 4 defines the estimator of OOS error and discusses
the properties of this estimator. Section 5 presents simulation results while Section 6 offers a discussion. Finally, Apendix A shows some useful existing results
and Apendix B contains the proofs of the obtained results.

2 Motivation
Geras and Sutton’s hypothesis that each source has the same number of elements
with each other is too restrictive (and some times not realistic) in practice. Also, the
construction of the decision rule based on all of the elements of the training set often
leads to various pathologies, as we see in the following example.
Example 1. Consider a data set of observations that are realizations of independent
variables and has size n = 30, say {Z1 , . . . , Z30 }. Assume that the data set arises
from three sources with n1 = n2 = n3 = 10 observations each; in general, denote
by n j the sample size associated with the jth source. A variable of the first source
follows N(−µ , 1), of the second source follows N(0, 1) and of the third source follows N(µ , 1). Let the squared error loss be used and suppose that a new variable
Z comes from the second source and is independent from the remaining variables
in the data set. Additionally, assume that the decision rule is the sample mean. According to Geras and Sutton’s (2013) formulation, Z has an OOS error which is
E(Z − Z 1,3 )2 , where Z 1,3 is the average of the union of the elements of the first and
1
third sources, that is Z 1,3 = 20
∑i∈S1 ∪S3 Zi , where S j denotes the set of indices of the
elements of the jth source. One can easily see that Z − Z 1,3 ∼ N(0, 1.05). Therefore,
E(Z − Z 1,3 )2 = Var(Z − Z 1,3 )+ E2 (Z − Z 1,3 ) = 1.05. Observe that in this case Geras
and Sutton’s formulation has the pathology that the preceding error is independent
of the value of µ . We see below, see Example 2, that the OOS error that is addressed
by Geras and Sutton (2013) is significantly different than the actual OOS error.

4

Afendras and Markatou

In view of the above, it is clear that we need to re-formulate the definition of the
OOS error in the context of multi-source data to take into account the fact that in
practice, not all sources have the same number of observations.

3 Framework and notation
Assume k sources, where k is a fixed number. Let a data set {Z1 , . . . , Zn } of size n be
observed by the following mechanism: The observations come from the sources that
follow a distribution p = (p1 , . . . , pk ). That is, the percentage of observations of the
jth source is p j , j = 1, . . . , k (the sample size of the jth source is n j = np j ). The vector of the numbers of observations of the sources is denoted by n = npp = (n1 , . . . , nk ).
Each Zi is labeled by its source and it is independent from the remaining observations whether those come from the same or different sources. The observations of
the jth source constitute an iid collection of size n j from an unknown distribution
Fj .
A new unobserved variable, say Z, comes from a source and is independent from
{Z1 , . . . , Zn }. The probability of the event “the variable Z belongs to the jth source”
is p j = n j /n, and follows the distribution Fj , j = 1, . . . , k. The OOS error is the error
that arises between the variable Z and the k − 1 foreign sources with respect to Z,
when a loss function L is used for measuring this error.
To formalize the above procedure, first we give a list of definitions and notations.
.
Let N = {1, . . . , n}. For each A ⊆ N, we denote by ZA the set ZA = {Zi | i ∈ A}.
The set of the indices of the jth source is denoted by S j and the set of observation
of this source is ZS j . The loss function L is a measurable nonnegative real function
b where db is a decision rule and T is the target variable. The decision rule is
L(T, d),
b A ), while the target variable
constructed using the elements of a set ZA , i.e. db= d(Z
b
b
b S ), j = 1, . . . , k, when
is an element Zi ∈
/ ZA . Hereafter, we write d j ≡ d j,n = d(Z
j
the decision rule is constructed based on the elements of the jth source and the total
sample size is n.
Since Zi s are independent and the elements of each source are identically distributed, the following are obvious.

E.1: L(Zi , dbl ), L(Zi′ , dbl ) , i ∈ S j , i′ ∈ S j′ with j 6= j′ 6= l 6= j, are exchangeable;

E.2: L(Zi , dbl ), L(Zi , dbl ′ ) , i ∈ S j with j 6= l 6= l ′ 6= j, are exchangeable;

E.3: L(Zi , dbl ), L(Zi′ , dbl ′ ) , i 6= i′ ∈ S j with j 6= l 6= l ′ 6= j, are exchangeable;

E.4: L(Zi , dbl ), L(Zi′ , dbj ) , i ∈ S j , i′ ∈ S j′ with j 6= j′ 6= l 6= j, are exchangeable.
E.5: L(Zi , dbl ) and L(Zi′ , dbl ′ ), i ∈ S j , i′ ∈ S j′ , are independent for all indices j, j′ , l, l ′
such that { j, l} ∩ { j′ , l ′ } = ∅.
Now we are in a position to present the algebraic form of the OOS error. Hereafter we assume that the loss function has finite moment of the first order; that is,
E|L(Zi , dbl )| < ∞ for all Zi ∈ Z j and l 6= j. Given that the variable Z comes from
the jth source and that the decision is constructed based on the elements of the lth

The out-of-source error in multi-source cross validation-type procedures

5

source, the error committed is
.
e j;l = E[L(Z, dbl )] when Z ∼ Fj and Z, ZSl are independent,

that is, e j;l is the expected value of the loss function when the decision rule is constructed based on the elements of the lth source and the target variable belongs to the
jth source and is independent of the elements of the lth source. Taking into account
the distribution of the sources and using the conditional total probability theorem,
given that the variable Z comes from the jth source the error is
.
ej =

1
pl e j;l ;
1 − p j l6∑
=j

this is the error that is created from an observation from the jth source when compared against observations from the other sources. According to the total probability
theorem, the total OOS error is defined by
k
k
(nn) .
µos = ∑ p j e j = ∑ od j ∑ pl e j;l ,
j=1

j=1

(1)

l6= j

.
where od j = p j /(1 − p j ) is the odds ratio of the jth source. This error can be thought
of as a generalization-type error.

4 The OOS error estimation
Here, we give an estimator of the OOS error defined in the previews section and
investigate the properties of this estimator.

4.1 Estimating the OOS error
We are interested in estimating the OOS error. To simplify notation we use ℓi, j to
denote L(Zi , dbj ). By definition, a natural estimator of e j;l is n1j ∑i∈S j ℓi,l , and thus, a
(nn)

natural estimator of µos is

k
1
(nn) . 1
bos
= ∑
nl ∑ ℓi,l .
µ
n j=1 n − n j l6∑
= j i∈S j

(2)

This estimator is a cross validation-type estimator of the OOS error. When k-fold
cross validation is used to estimate generalization error the data are split in k equal
parts. Each of these parts is a test set and its complement set is the corresponding
training set. The target variable is a variable of the test set and the decision rule

6

Afendras and Markatou

is constructed based on the elements of the corresponding training set (for more
details see, for example, Afendras and Markatou, 2016). Here, we have k test sets
(ZS1 , . . . , ZSk ), which are defined by the labeling of the data and are a partitioning
S
of the data set. For each test set ZS j the corresponding training set ZScj = l6= j ZSl
is partitioned into k − 1 training sub-sets ZS1 , . . . , ZS j−1 , ZS j+1 , . . . , ZSk . The target
variable is a variable of the test set and for each l 6= j the decision rule is constructed
based on the elements of the training sub-set ZSl .
(nn)
(nn)
bos
bos instead µos
and µ
respectively. The following
Hereafter we write µos and µ
example illustrates the difference between the OOS error that introduced by Geras
and Sutton and that we have defined in relationship (1).
Example 2 (Example 1 continued). Let the data be as in Example 1 and the squared
error loss is used. Let us consider Z (1) ∼ N(− µ , 1), Z (2) ∼ N(0, 1), Z (3) ∼ N(µ , 1)
and Z (1) , Z (2) , Z (3) , {Z1 , . . . , Zn } are independent. Then, Z (1) −Z 2,3 ∼ N(−3µ /2, 1.05),
Z (2) − Z 1,3 ∼ N(0, 1.05) and Z (3) − Z 1,2 ∼ N(3µ /2, 1.05). Hence, the OOS error
given by Geras and Sutton (2013) is

µCVS =

2
2
2 o
3
1n
= 1.05 + µ 2 .
E Z (1) − Z 2,3 + E Z (2) − Z 1,3 + E Z (3) − Z 1,2
3
2

Using the more general Example 4(a) below, relation (3) gives that the OOS error
given by (1) is µos = 1.1 + 2µ 2.

bos
4.2 Bias and variance of µ

In this section we investigate the bias and variance, and so the mean square error, of
bos . In view of E.1–E.5, we state and prove the following
the OOS error estimator µ
theorem.

Theorem 1. Assume that E[L(Z, dbl )]2 < ∞ when Z ∼ Fj and Z, ZSl are independent
for all j 6= l. Then,
bos given by (2) is an unbiased estimator of the OOS error;
(a) the estimator µ
bos is
(b) the variance of µ
k

bos ) = ∑
Var(µ

od 2j

j=1 np j

∑

p2l

l6= j

+ ∑∑ od j od j′
j6= j ′



V j;l + n(p j − 1/n)C j;l + ∑∑ pl pl ′ C j;l,l ′
l6=l ′ : l,l ′ 6= j

!

∑ pl (pl C j, j′ ;l + 2p j C j, j′ ;l, j )

l6= j, j ′

!

,

where V j;l = Var L(Z, dbl ) when Z ∼ Fj and is independent of ZSl ; C j;l =
Cov(L(Z, dbl ), L(Z ′ , dbl )) when Z and Z ′ are iid from Fj and are independent
of ZSl ; C j;l,l ′ = Cov(L(Z, dbl ), L(Z, dbl ′ )) when Z ∼ Fj and is independent of

The out-of-source error in multi-source cross validation-type procedures

7

ZSl ∪ZSl ′ ; C j, j′ ;l = Cov(L(Z, dbl ), L(Z ′ , dbl )) when Z ∼ Fj , Z ′ ∼ Fj′ and Z, Z ′ , ZSl
are independent; and C j, j′ ;l, j = Cov(L(Z, dbl ), L(Z ′ , dbj )) when Z ∈ ZS j , Z ′ ∼ Fj′
and Z ′ , ZS j , ZSl are independent.

bos . First, we are interested
Now we investigate the consistency of the estimator µ
in finding simple and natural conditions that imply the desired result. Very often the
sequence, with respect to n, of the decision rules dbj;n converges in probability to
a constant for each j. For example, if the decision rule is the sample mean of the
p
elements of the jth source, say Z j , and Fj has mean µ j , then Z j −→ µ j . Also, the
finiteness of the variance of the OOS error estimator requires that E[L(Zi , dbl )]2 < ∞
for all Zi ∈ ZS j and j 6= l. In view the above observations, we state the following
conditions/assumptions:
p
C.1: dbj;n −→ d j , as n → ∞, for all j = 1, . . . , k, where d j s are constants.
C.2: There exist θ , M > 0 such that E[L(Z, dbl,n )]2+θ ≤ M when Z ∼ Fj and Z, ZSl
are independent, for all j 6= l and n.

Theorem 2. Let L be a continuous loss function and suppose that C.1, C.2 hold.
bos ) → 0 as n → ∞ and, thus, µ
bos is a consistent estimator of µos .
Then, Var(µ
The following Examples 3 and 4 show the usefulness of Theorem 2.

Example 3. Let ZS j be an iid collection of random variables (rv’s) from Fj , j =
1, . . . , k, the decision rules are the usual averages of the elements of the sources, Fj
does not depend on n and has mean µ j and variance σ 2j .
(a) Let the absolute error loss be used. Suppose that Fj has finite moments of order
p
2 + θ j for some θ j > 0, j = 1, . . . , k. Then, dbj = Z j = n1j ∑i∈S j Zi −→ µ j , that

is, C.1 is satisfied. Set θ = min j=1,...,k {θ j } > 0, β2+θ = max j=1,...,k {E|Z|2+θ
when Z ∼ Fj } < ∞ and M = 23+θ β2+θ < ∞. For each j 6= l and Z ∼ Fj such
b 2+θ = E|Z − Z l |2+θ ≤
that Z, ZSl are independent we have
 that E|L(Z, dl,n )|


22+θ E|Z|2+θ + E|Z l |2+θ ≤ 22+θ E|Z|2+θ + n1 ∑i∈Sl E|Zi |2+θ ≤ 23+θ β2+θ =
l
bos ) =
M; and so C.2 is satisfied. Therefore, Theorems 1 and 2 show that MSE(µ
bos ) = Var(µ
bos ) → 0 as n → ∞.
bos ) + Var(µ
bias2 (µ
(b) Let the squared error loss be used, that is L(Z, dbl,n ) = (Z − Z l )2 , and suppose that
Fj has finite moments of order 4 + θ j for some θ j > 0, j = 1, . . . , k. Using the
bos ) → 0 as n → ∞.
same arguments as in (a), we obtain that MSE(µ
Example 4. Suppose Fj ∼ N(µ j , σ 2j ) and dbj = Z j = n1j ∑i∈S j Zi .
(a) Let the squared error loss be used. Then, we calculate (see in Apendix B)
k

k

j=1

j=1

µos = ∑ p j σ 2j + ∑ od j ∑ pl (µ j − µl )2 +
l6= j

1 k
∑ od j ∑ σ 2j ;
n j=1
l6= j

(3)

and the quantities V j;l , C j;l , C j;l,l ′ C j, j′ ;l and C j, j′ ;l, j that appear in the variance
bos in Theorem 1(b) are
of µ

8

Afendras and Markatou

V j;l




σ2
σ2
σ j + l + 2(µ j − µl )2 ,
= 2 σj + l
npl
npl

C j;l = 2

σl2
npl




σl2
+ 2(µ j − µl )2 ,
npl
















C j;l,l ′ = 2σ 2j σ 2j + 2(µ j − µl )(µ j − µl ′ ) ,


σl2 σl2
C j, j′ ;l = 2
+ 2(µ j − µl )(µ j′ − µl ) , 


npl npl

!


2
2

σj
σj


C j;l,l ′ = 2
− 2(µ j − µl )(µ j′ − µ j ) .

np j np j

(4a)

(4b)

Observe that C j;l , C j, j′ ;l , C j, j′ ;l, j → 0 as n → ∞; specifically, these covariances
bos ) = O(1/n) as n → ∞.
are O(1/n) functions as n → ∞. It is obvious that Var(µ
This example is a confirmation of Theorem 2 for this case.
(b) Let the absolute error loss be used. Then, see in Apendix B,
!)
(
r



k
µ 2j;l
µ j;l
2
+ σ j;l
, (5)
µos = ∑ od j ∑ pl µ j;l 1 − 2Φ −
exp − 2
σ j;l
π
2σ j;l
j=1
l6= j
where µ j;l = µ j − µl , σ 2j;l = σ 2j + σl2 /(npl ) and Φ denotes the cumulative distribution function of the standard normal distribution. The calculations of the
covariances C j;l , C j;l,l ′ , C j, j′ ;l and C j;l,l ′ in Theorem 1(b) are rather difficult.
In practice, the data distributions of the sources are unknown and, thus, the OOS
error must be estimated. They are loss function for which the calculation of the
bos is difficult, or impossible, even if the distribution of the data sources
variance of µ
is known, cf. Example 3(b). Furthermore, in the formulation of Example 3 where the
absolute error loss is used, if we consider Fj ∼ U(a j , b j ), j = 1, 2, 3, the calculation
of OOS error in closed form is impossible.

4.3 On variance estimation
Here we investigate the possibility of the variance estimation of the OOS error.
First, we present a general result and some useful observations that arise from it.
Nadeau and Bengio (2003) study the variance estimation of the random cross validation estimator of the generalization error of a computer algorithm when L(Zi , dbj )
for all realizations ZS j and Zi ∈ ZScj are exchangeable. They prove that “There is
no general unbiased estimator of the variance of the random cross validation estimator that involves the L(Zi , dbj )s in a quadratic and/or linear way.” (see Nadeau and
Bengio, 2003, Proposition 3, page 246). This result holds in a more general form.
Lemma 1. Let X1 , X2 , . . . , Xn be a collection of random variables. If E(X j ) = µ ,
Var(X j ) = σ 2 and Cov(X j , X j′ ) = C, j 6= j′ , are unknown parameters, then we can

The out-of-source error in multi-source cross validation-type procedures

9

find unbiased estimators of the second moments of X j s only for the cases of linear
combinations of σ 2 + µ 2 , C + µ 2.
The following corollary follows immediately from Lemma 1.
Corollary 1. Let X1 , X2 , . . . , Xn be as in Lemma 1. Then, (a) there does not exist an
unbiased estimator of Var(X), where X is the usual average of X j s, and (b) there do
not exist unbiased estimators of µ 2 , σ 2 , C.
Remark 1. (a) If one of the parameters µ 2 , σ 2 and C is known, then we can provide
unbiased estimators for each linear combination of the other two parameters.
1
(b) The statistic s2 = n−1
∑nj=1 (X j − X)2 is an unbiased estimator of σ 2 − C. The
variance of this estimator is
)
(
n

1
2
2
2
2
Var(s ) =
∑ Var(X j − X) + ∑∑′ Cov (X j − X) , (X j′ − X) .
(n − 1)2 j=1
1≤ j< j ≤n

It is possible Var(s2 ) 6→ 0, as n → ∞, see Example 5 below; and thus, s2 is not
consistent estimator of σ 2 − C.
(c) In both random and k-fold cross validation estimators of the generalization error of a computer algorithm, the sequence of the test set errors are as in Lemma 1
(see Afendras and Markatou, 2016, Proposition 1). For both of these cases the cross
validation estimator is the usual average of the test set errors. Thus, the unbiased esb j, j =
timation of the variance of the cross validation estimator is impossible. Let µ
bCV,J = J1 ∑Jj=1 µ
b j be the cross validation esti1, . . . , J, denote the test set errors and µ
1
bCV,J ) and
bj − µ
mator in the random cross validation procedure. If s2µb = J−1
∑Jj=1 (µ
j


b j, µ
b j′ ), Nadeau and Bengio (2003, p. 248) state that “. . . 1 + 1−ρ ρ s2µb is
ρ = Corr(µ
j
bCV,J )”; this sentence is incorrect because the paraman unbiased estimator of Var(µ
eter ρ is unknown and, thus, 1 + 1−ρ ρ s2µb is not an estimator (statistic). Of course,
h
j
i
ρ
bCV,J ). In general, the estiit is a random variable with E 1 + 1−ρ s2µb = Var(µ
j
mation of the correlation ρ is difficult. Nevertheless,
even

 in the case in which we
ρb
find an unbiased estimator of ρ , say ρb, then 1 + 1−bρ s2µb is not an unbiased estij


ρb
2
b
mator of Var(µCV,J ), except if 1 + 1−bρ and sµb are uncorrelated. Moreover, if ρb
j


ρb
2 might is not a consistent estimator
is consistent estimator of ρ , then 1 + 1−b
s
bj
µ
ρ
bCV,J ), cf. (b).
of Var(µ

(d) Markatou et al. (2005) provide moment approximation estimators for the variance of the test set errors and for their covariance in a broad and often used class
of cross validation procedures, in both random and k-fold cross validation cases. In
view of (c), it is clear that their results are very important in practice.

10

Afendras and Markatou

Example 5. Let 0 < C < σ 2 < ∞ and µ ∈ R. Assume that Y1 , . . . ,Yn is an iid collec
tion from the distribution with probability mass function pY −(σ 2 − C)1/2/2 =



pY (σ 2 − C)1/2/2 = (n2 − 1)/(2n2 − 1/2), pY −n(σ 2 − C) = pY n(σ 2 − C) =
3/(8n2 − 2); and ε ∼ N(µ , C) which is independent to Y j s. By straightforward
calculations, E(Y ) = 0, Var(Y ) = σ 2 − C. Consider the rv’s X j = Y j + ε , j =
1, . . . , n. Then, one can easily see that the X j s are exchangeable with E(X j ) =
µ , Var(X j ) = σ 2 and Cov(X j , X j′ ) = C for all j 6= j′ . By definition of the X j s,
1
1
n
n
2
n−1 ∑ j=1 (X j − X) = n−1 ∑ j=1 (Y j − Y ) = sY . So,
4 +n2 −1
σ 2 −C)
(n−3) Var(Y )
= 12n
+ (n−3)(
→ ∞ as n → ∞.
n(n−1)
n(n−1)
n(16n2 −4)

s2X =

Var(s2X ) = Var(sY2 ) =

(Y )

µ4
n

+

In view of Theorem 1(a), Lemma 1 and Corollary 1, the unbiased estimation of
bos is impossible because the quantities V j;l , C j;l , C j;l,l ′ , C j, j′ ;l and
the variance of µ
C j, j′ ;l, j are as in Lemma 1. For example, let the jth source and the lth source be two
deferent sources. Then, {ℓi,l , i ∈ S j } is a set of exchangeable rv’s of size n j with
unknown mean, say µ j,l , variance V j,l and covariance between two elements C j,l .
It is a fact that there does not exist a general unbiased estimator of the variance
of the OOS error. If someone needs an estimator of the variance of the OOS error
for some reason (for example, for statistical inference on the OOS error), one may
resort to the bootstrap resampling technique or can follow the moment approximation method of Markatou et al. (2005) when it is possible. Notice that the bootstrap
resampling technique in this formulation has a very large computational cost.

5 Simulation study
Assume we have k = 3 sources with probability vector p = (0.2, 0.3, 0.5), and thus
odds vector od = (1/4, 3/7, 1). Suppose that the elements of each source are iid rv’s
from a distribution and the squared or absolute error loss is used.
Table 1 presents the true value of the OOS error, the empirical mean and the embos , when N = 104 Monte
pirical mean squared error of the OOS error estimator µ
Carlo (M-C) repetitions are used, for various values of the sample size n. The elements of each source are normally distributed and the squared and absolute error
loss are used. In this case we have the explicit expressions of µos given by the relations (3) and (5) for both cases of squared and absolute error loss respectively.
We observe that for both cases, squared and absolute error loss, the empirical mean
bos tends to zero as n tends to infinity, confirming the statements of
square error of µ
Theorems 1(a) and 2.
Tables 2–4 present the empirical mean and the empirical variance of the OOS
bos , for N = 104 M-C repetitions for various values of the sample
error estimator µ
size n, when the elements of each source are uniformly distributed (Table 2), Student
distributed (Table 3) and gamma distributed (Table 4), and the squared and absolute
error loss are used. For both cases of loss function, squared and absolute error loss,
bos
and for all cases of the sources’ distributions the empirical empirical variance of µ

The out-of-source error in multi-source cross validation-type procedures

11

absolute

squared

[ µos ), for
bos and its empirical mean square error MSE(b
Table 1 The OOS error, µos , the average of µ
N = 104 M-C repetitions, when k = 3, p = (0.2, 0.3, 0.5), F1 ∼ N(0, 9), F2 ∼ N(2, 1), F3 ∼ N(5, 5)
and the squared/absolute error loss is used, for various values of n.
n
µos
bos
µ
d 2 (b
µos )
bias
d µos )
Var(b
[ µos )
MSE(b
µos
bos
µ
d 2 (b
µos )
bias
d
µos )
Var(b
[ µos )
MSE(b

100
18.171
18.164
< 10−3
11.524
11.524
3.639
3.635
< 10−5
0.148
0.148

200
18.084
18.084
< 10−3
5.897
5.897
3.636
3.634
< 10−5
0.074
0.074

300
18.055
18.055
< 10−4
3.873
3.873
3.635
3.638
< 10−5
0.050
0.050

500
18.031
18.038
< 10−4
2.314
2.314
3.635
3.635
< 10−5
0.030
0.030

700
18.021
18.038
< 10−5
1.664
1.664
3.634
3.633
< 10−6
0.021
0.021

103
18.014
18.017
< 10−5
1.177
1.177
3.634
3.634
< 10−7
0.014
0.014

104
17.998
17.999
< 10−6
0.117
0.117
3.633
3.633
< 10−8
0.001
0.001

tends to zero as n tends to infinity, confirming empirically the statement of Theorem
2. Note that for these cases of the sources’ distributions we do not have explicit
d 2 (µ
[ µ
bos ) and MSE(
bos ). On
forms of µos and thus, we cannot present the values bias
bos is an unbiased estimator of µos , for large values of n we
the other hand, since µ
[ µ
bos ) ≈ d
bos ).
have that MSE(
Var(µ

d µos ), for N = 104 M-C repetitions, when
bos and its empirical variance Var(b
Table 2 The average of µ
k = 3, p = (0.2, 0.3, 0.5), F1 ∼ U(−1, 1), F2 ∼ U(1/2, 3/2), F3 ∼ U(3, 7) and the squared/absolute
error loss is used, for various values of n.
n
bos
d µ
e
r
a
d µos )
squ
Var(b
bos
te µ
olu
d µos )
Var(b
abs

100
17.294
1.699
3.8435
0.0229

200
17.266
0.871
3.8451
0.0113

300
17.277
0.568
3.8425
0.0077

500
17.271
0.332
3.8433
0.0047

700
17.273
0.243
3.8433
0.0033

103
17.278
0.173
3.8430
0.0022

104
17.275
0.017
3.8428
0.0002

d µos ), for N = 104 M-C repetitions,
bos and its empirical variance Var(b
Table 3 The average of µ
d

when k = 3, p = (0.2, 0.3, 0.5), F1 ∼ t7 , F2 ∼ t5 (2), F3 ∼ t6 (5) (where tν (µ ) = tν + µ ) and the
squared/absolute error loss is used, for various values of n.
n
bos
d µ
e
r
a
d µos )
squ
Var(b
bos
te µ
olu
d µos )
Var(b
abs

100
14.976
2.677
3.5182
0.0417

200
14.927
1.376
3.5142
0.0209

300
14.954
0.941
3.5153
0.0141

500
14.943
0.548
3.5152
0.0084

700
14.936
0.388
3.5150
0.0061

103
14.936
0.274
3.5153
0.0042

104
14.925
0.027
3.5147
0.0004

12

Afendras and Markatou

d µos ), for N = 104 M-C repetitions,
bos and its empirical variance Var(b
Table 4 The average of µ
when k = 3, p = (0.2, 0.3, 0.5), F1 ∼ exp(1), F2 ∼ Γ (2, 1), F3 ∼ Γ (10, 2) and the squared/absolute
error loss is used, for various values of n.
n
bos
µ
d
e
ar
d µos )
squ
Var(b
bos
te µ
olu
d µos )
Var(b
abs

100
12.095
2.763
3.0669
0.0469

200
12.068
1.326
3.0636
0.0240

300
12.067
0.863
3.0655
0.0163

500
12.060
0.537
3.0662
0.0095

700
12.038
0.385
3.0657
0.0070

103
12.048
0.265
3.0647
0.0048

104
12.043
0.027
3.0652
0.0005

6 Discussion
In this paper we discuss the definition, estimation and properties of the proposed
estimator of the out-of-source error in the context of multi-source data, when it is
not assumed that all sources have exactly the same number of observations and do
not necessarily follow the same distribution. We show that our proposed estimator is
unbiased, and we offer natural and easy to verify in practice conditions under which
the estimator we propose is consistent.
Most research, both theoretical and empirical, assumes that a learning algorithm
is trained and tested using data that follow the same distribution. This setting has
been extensively studied in the literature, and uniform convergence theory guarantees that a learning algorithm’s empirical error is close to its true error under appropriate assumptions. However, in many practical situations we wish to train a learning
algorithm under one or more source domains and then test it on a domain that is potentially different from the source domains. Our work, presented here, studies the
out-of-source error in this setting. We further supplement the theoretical results we
present here with a simulation that essentially verifies these results.
Acknowledgements Dr. Markatou would like to thank the Jacobs School of Medicine and
Biomedical Science for facilitating this work through institutional financial resources (to M.
Markatou) that supported the work of the first author of this paper.

Apendix A On moments of bivariate normal distribution
  2
Theorem A.1 (Isserlis, 1918). Let (Y1 ,Y2 ) ∼ N2 0 , σσ121

σ12
σ22

2 and E(Y 2Y ) = E(Y Y 2 ) = 0.
3σi4 , E(Y12Y22 ) = σ12 σ22 + 2σ12
1 2
1 2



. Then, E(Yi4 ) =

An application of Isserlis’s Theorem A.1 gives

   2
µ1
σ1 σ12
. Then, the covariance of X12
Corollary A.1. Let (X1 , X2 ) ∼ N2
µ2 , σ12 σ 2

and X22 is Cov(X12 , X22 ) = 2σ12 (σ12 + 2µ1 µ2 ).

2

The out-of-source error in multi-source cross validation-type procedures

13

Apendix B Proofs
Proof of Theorem 1. (a) By definition of e j;l ,
bos ) =
E(µ

1 k
1
1 k nj
nl ∑ E(ℓi,l ) = ∑
nl e j;l .
∑
∑
n j=1 n − n j l6= j i∈S j
n j=1 n − n j l6∑
=j

The result arises by n j /n = p j for all j = 1, . . . , k.
bos =
(b) Write Σ j = ∑l6= j nl ∑i∈S j ℓi,l and Σ j,l = ∑i∈S j ℓi,l . Hence, µ
and Σ j = ∑l6= j nl Σ j,l . By straightforward calculations
1
bos ) = 2
Var(µ
n

(

Cov(Σ j , Σ j′ )
Var(Σ j )
∑ (n − n j )2 + ∑∑′ (n − n j )(n − n j′ )
j=1
j6= j
k

1
n

)

1
Σj
∑kj=1 n−n
j

.

(B.1)

The variance of Σ j is Var(Σ j ) = ∑l6= j n2l Var(Σ j,l )+ ∑ ∑l6=l ′ : l,l ′ 6= j nl nl ′ Cov(Σ j,l , Σ j,l ′ ).
We compute Var(Σ j,l ) = ∑i∈S j Var(ℓi,l ) + ∑ ∑i,i′ ∈S j : i6=i′ Cov(ℓi,l , ℓi′ ,l ) = n j V j;l +
n j (n j − 1)C j;l , see E.1 and E.2. Also, we compute the covariance of Σ j,l and Σ j,l ′ ,
Cov(Σ j,l , Σ j,l ′ ) = ∑i∈S j Cov(ℓi,l , ℓi,l ′ ) + ∑ ∑i,i′ ∈S j : i6=i′ Cov(ℓi,l , ℓi′ ,l ′ ) = n j C j;l,l ′ , see
E.3 and E.5. Thus,

Var(Σ j ) = ∑ n2l n j V j;l + n j (n j − 1)C j;l + ∑∑ n j nl nl ′ C j;l,l ′ .
(B.2)
l6=l ′ : l,l ′ 6= j

l6= j

The covariance of Σ j and Σ j′ is Cov(Σ j , Σ j′ ) = ∑l6= j ∑l ′ 6= j′ nl nl ′ Cov(Σ j,l , Σ j′ ,l ′ ) =
∑l6= j, j′ n2l Cov(Σ j,l , Σ j′ ,l ) + ∑ ∑l6= j,l ′ 6= j′ : l6=l ′ nl nl ′ Cov(Σ j,l , Σ j′ ,l ′ ). Now we compute
Cov(Σ j,l , Σ j′ ,l ) = ∑i∈S j ∑i′ ∈S j′ Cov(ℓi,l , ℓi′ ,l ) = n j n j′ C j. j′ ;l . For Cov(Σ j,l , Σ j′ ,l ′ ) when
l 6= l ′ we distinguish the following cases: If l 6= j′ and l ′ 6= j, Cov(Σ j,l , Σ j′ ,l ′ ) = 0, see
E.5; if l 6= j′ and l ′ = j, Cov(Σ j,l , Σ j′ , j ) = ∑i∈S j ∑i′ ∈S j′ Cov(ℓi,l , ℓi′ , j ) = n j n j′ C j, j′ ;l, j ,
see E.4; and if l = j′ and l ′ 6= j, similarly, Cov(Σ j, j′ , Σ j′ ,l ′ ) = n j n j′ C j, j′ ; j′ ,l ′ . Thus,
for each j 6= j′
Cov(Σ j , Σ j′ ) = ∑ nl n j n j′ (nl C j, j′ ;l + 2n j C j, j′ ;l, j )
l6= j, j ′

Combining (B.1)–(B.3),


n2l n j V j;l + n j (n j − 1)C j;l + ∑∑ n j nl nl ′ C j;l,l ′
∑


k l6= j
1
l6=l ′ : l,l ′ 6= j
bos ) = 2 ∑
Var(µ
2
n 
(n − n j )
j=1

∑ nl n j n j′ (nl C j, j′ ;l + 2n j C j, j′ ;l, j ) 

l6= j, j ′
+ ∑∑
.

(n − n j )(n − n j′ )

j6= j ′

(B.3)

14

Afendras and Markatou

Using n j = np j and od j = p j /(1 − p j ) for all j, after some algebra, the proof is
completed.
⊓
⊔
Proof of Lemma 1. Since the joint distribution function of X j s is unknown, the
only information that we have is with respect to the moments of X j s. Therefore,
the only forms of estimators that we know to have expected values equal to linear
combinations of µ 2 , σ 2 and C are the linear combination of X j2 s and X j X j′ s. Consider δ = ∑nj=1 a j X j2 + ∑ ∑1≤ j< j′ ≤n b j, j′ X j X j′ . Observe that E(X j2 ) = σ 2 + µ 2 and
E(X j X j′ ) = C + µ 2. Thus, setting a = ∑nj=1 a j and b = ∑ ∑1≤ j< j′≤n b j, j′ , we get
E(δ ) = a(σ 2 + µ 2 ) + b(C + µ 2),
⊓
⊔

completing the proof.

Proof of Corollary 1. (a) We compute Var(X) = 1n σ 2 + n−1
n C. Let now δ be an
unbiased estimator of the variance of X, δ = ∑nj=1 a j X j2 + ∑ ∑1≤ j< j′ ≤n b j, j′ X j X j′ .
Setting a = ∑nj=1 a j and b = ∑ ∑1≤ j< j′ ≤n b j, j′ , we get


1 2 n−1
1
1
a(σ + µ ) + b(C + µ ) = σ +
C ⇒ a = , b = 1− , a+b = 0 ,
n
n
n
n
2

2

2

a contradiction.
⊓
⊔

(b) Using the same arguments as in (a), the proof is completed.

Proof of Theorem 2. Let Z ∼ Fj be independent of the elements of the lth source.
Using Hölder inequality and C.2, V j,l ≤ E[L(Z, dbl,n )]2 ≤ E{[L(Z, dbl,n )]2+θ }2/(2+θ ) ≤
od 2

od 2

M 2/(2+θ ) = M ∗ for all j 6= l. Thus, ∑kj=1 npjj (∑l6= j p2l V j;l ) ≤ Mn ∑kj=1 p jj (∑l6= j p2l ) =
O(1/n). An application of Cauchy–Schwarz inequality gives |C j,l,l ′ | ≤ V j,l ≤ M ∗ .
od 2

∗

∗

od 2

So, ∑kj=1 npjj (∑ ∑l6=l ′ : l,l ′ 6= j pl pl ′ C j;l,l ′ ) ≤ Mn ∑kj=1 p jj (∑ ∑l6=l ′ : l,l ′ 6= j pl pl ′ ) = O(1/n).
It is remains to prove that C j;l , C j, j′ ,l , C j, j′ ;,l, j → 0 as n → ∞. Let Z, Z ′ are iid from
Fj and are independent of the elements of the lth source. Consider the sequence
of random vectors (Z, Z ′ , dbl,n ) with respect to n. Then, C.1 gives (Z, Z ′ , dbl,n )
(Z, Z ′ , dl ) as n → ∞. Since L is continuous, the maps (Z, Z ′ , dbl,n ) 7→ L(Z, dbl,n )
and (Z, Z ′ , dbl,n ) 7→ L(Z, dbl,n )L(Z ′ , dbl,n ) are continuous. Using the Continuous Mapping Theorem, L(Z, dbl,n ) L(Z, dl ) and L(Z, dbl,n )L(Z ′ , dbl,n ) L(Z, dl )L(Z ′ , dl ) as
n → ∞. Observe that E|L(Z, dbl,n )|1+(1+θ ) ≤ M, see C.2, so the sequence L(Z, dbl,n )
is uniformly integrable. Hence, E|L(Z, dl )| < ∞ and E[L(Z, dbl,n )] → E[L(Z, dl )]
as n → ∞ (see, e.g., Billingsley, 1995, p. 338). Similarly, E|L(Z ′ , dl )| < ∞ and
E[L(Z ′ , dbl,n )] → E[L(Z ′ , dl )] as n → ∞. Using Cauchy–Schwarz inequality we obtain E|L(Z, dbl,n )L(Z ′ , dbl,n )|1+θ /2 ≤ (E|L(Z, dbl,n )|2+θ )1/2 (E|L(Z ′ , dbl,n )|2+θ )1/2 ≤ M.
So, L(Z, dbl,n )L(Z ′ , dbl,n ) is uniformly integrable. Therefore, E|L(Z, dl )L(Z ′ , dl )| < ∞
and E[L(Z, dbl,n )L(Z ′ , dbl,n )] → E[L(Z, dl )L(Z ′ , dl )] as n → ∞. Moreover, L(Z, dl ) and

The out-of-source error in multi-source cross validation-type procedures

15

L(Z ′ , dl ) are independent. So, E[L(Z, dbl,n )L(Z ′ , dbl,n )] → E[L(Z, dl )]E[L(Z ′ , dl )] as
n → ∞. From the preceding analysis we have that C j;l → 0 as n → ∞. Using the
same arguments as above it follows that C j, j′ ,l , C j, j′ ;,l, j → 0 as n → ∞, and the proof
is completed.
⊓
⊔
Proof of Equations (3)–(5). Let j, j′ , l, l ′ are four distinct indices. Assume that
Z( j) , Z(′ j) ∈ ZS j (with Z( j) 6= Z(′ j) ) and Z( j′ ) ∈ ZS j′ . Consider the following random


  σ 2 +σ 2 /n
σl2 /nl
µ j − µl
l
j
l
vectors (X1 , X2 ) = (Z( j) − Z l , Z(′ j) − Z l ) ∼ N2
,
,
µ j − µl
σ 2j +σl2 /nl
σl2 /nl



 σ 2 +σ 2 /n
σ 2j
l
µ j − µl
j
l
(X3 , X4 ) = (Z( j) −Z l , Z( j) −Z l ′ ) ∼ N2
, (X5 , X6 ) =
2
2
µ j − µl ′ ,
σj
σ j +σl2′ /nl ′



 σ 2 +σ 2 /n
σl2 /nl
l
µ j − µl
j
l
, (X7 , X8 ) = (Z( j) −
(Z( j) − Z l , Z( j′ ) − Z l ) ∼ N2
2
2
µ j′ − µl ,
σ j′ +σl2 /nl
σl /nl

  σ 2 +σ 2 /n −σ 2 /n 
j
l
µ j − µl
j
j
l
. If X ∼ N(µ , σ 2 ), then
Z l , Z( j′ ) − Z j ) ∼ N2
2
2
2
µ ′ −µ j ,
σ j′ +σ j /n j
Since V j,l = Var(X12 ), (4a) follows. Observe that C j;l =
2
2
Cov(X1 , X2 ), C j;l,l ′ = Cov(X32 , X42 ), C j, j′ ;l = Cov(X52 , X62 ) and C j, j′ ;l, j = Cov(X72 , X82 ).
Hence, an application of Corollary A.1 proves (4b). Finally, If X ∼ N(µ , σ 2 ), then
j

−σ j /n j

Var(X 2 ) = 2σ 2 (σ 2 + 2µ 2).

2
2
E|X| = µ [1 − 2Φ (− µ /σ )] + σ (2/π )1/2 exp{−
 Because e j;l = E|X1 | =
 µ /(2σ )}.
p


2
2
µ j;l 1 − 2Φ −µ j;l /σ j;l + σ j;l 2/π exp −µ j;l /2σ j;l , using (1), (5) follows,
completing the proof.
⊓
⊔

Proof
 A.1. Consider Y1 = X1 − µ1 and Y2 = X2 − µ2 . Then, (Y1 ,Y2 ) ∼
 of
 Corollary
σ12 σ12
N2 0 , σ12 σ 2 . Thus, Cov(X12 , X22 ) = Cov(Y12 + 2µ1Y1 + µ12 ,Y22 + 2µ2Y2 + µ22 ) =
2

Cov(Y12 ,Y22 ) + 2µ2 Cov(Y12 ,Y2 ) + 2µ1 Cov(Y1 ,Y22 ) + 4µ1 µ2 Cov(Y1 ,Y2 ). A simple application of Isserlis’s Theorem completes the proof.
⊓
⊔

References
Afendras, G. and Markatou, M. (2016). Optimality of Training/Test Size and Resampling Effectiveness of Cross-Validation Estimators of the Generalization Error. arXiv:1511.02980v1 [math.ST]
Arlot, S. and Celisse, A. (2010). A survey of cross-validation procedures for model
selection. Statistics Surveys, 4, 40–79.
Ben-David, S., Blitzer, J, Crammer, K., Kulesza, A., Pereira, F. and Vaughan, J.W.
(2010). A theory of learning from different domains. Mach. Learn., 79, 151–175.
Bengio, Y. and Grandvalet, Y. (2004). No unbiased estimator of the variance of kfold cross validation. Journal of Machine Learning Research, 5, 1089–1105.
Breiman, L., Friedman, J.H., Olshen, R.A. and Stone, C.J. (1984). Classification
and Regression Trees. Wadsworth, Belmont, California.

16

Afendras and Markatou

Billingsley, P. (1995). Probability and Measure. Third Edition. Wiley Series in Probability and Mathematical Statistics.
Geisser, S. (1975). The predictive sample reuse method with applications. Journal
of the American Statistical Association, 70(350), 320–328.
Geras, K. and Sutton, C. (2013). Multiple-source cross-validation. Proceedings of
the 30 th International Conference on Machine Learning, Atlanta, Georgia, USA,
2013. JMLR: W&CP, 28(3), 1292–1300.
Isserlis, L. (1918). On a formula for the product-moment coefficient of any order
of a normal frequency distribution in any number of variables. Biometrika, 12,
134–139.
Markatou, M., Tian, H, Biswas, S. and Hripcsak, G. (2005). Analysis of Variance of
Cross-Validation Estimators of the Generalization Error. J. Mach. Learn. Res., 6,
1127–1168.
Nadeau, C. and Bengio, Y. (2003). Inference for the generalization error. Mach.
Learn., 52, 239–281.
Stone, M. (1974). Cross-validatory choice and assessment of statistical predictions.
Journal of the Royal Statistical Society. Series B, 36(2), 111–147.
Stone, M. (1977). Asymptotics for and against cross-validation. Biometrika, 64(1),
29–35.

