Towards Enabling Learnware to Handle Unseen Jobs∗
Yu-Jie Zhang, Yu-Hu Yan, Peng Zhao, Zhi-Hua Zhou
National Key Laboratory for Novel Software Technology,
Nanjing University, Nanjing 210023, China{zhangyj, yanyh, zhaop, zhouzh}@lamda.nju.edu.cn

Abstract

Introduction

Nowadays, machine learning models have shown impressive
power in handling various jobs. However, when training awell-performed model, numerous data, fast machines, andexpertise are always required, making it quite struggling tolearn from scratch. The expensive cost has been a burden
for users who hope to deploy learning models in their jobs.
As there have already been vast well-performed models developed by different individuals, a natural question arises:
Is it possible to build a model sharing platform, following a
protocol to help the user benefit from existing models?
Zhou (2016) considers running a learnware market shownas Figure 1. A learnware is a high-quality model associatedwith its specification served as an explanation or specialty forthe model. There are two parts of participants in the market.
The first is the developers, who could individually accessthe raw data for various learning jobs. Based on the local∗

This research was supported by NSFC (61921006)
Copyright c 2021, Association for the Advancement of Artificial
Intelligence (www.aaai.org). All rights reserved.

specification

Job 1

learnware 2: (𝑓𝑓2 , 𝜇𝜇�2 )specification
Job 2
email

“abc”

…

Spam?

0

…

0

1

…

1

1

…

0

Job C

“abc”> 0.8

spam“abc”≤ 0.8

email“our”> 1.2

spam

Current job…

1

Deploying Stage

learnware 1: (𝑓𝑓1 , 𝜇𝜇�1 )…

The learnware (Zhou 2016) paradigm attempts to change thecurrent style of machine learning deployment, i.e., user builds
her own machine learning application almost from scratch,
to a style where the previous efforts of other users can bereused, given a publicly available pool of machine learningmodels constructed by previous users for various tasks. Eachlearnware is a high-quality pre-trained model associated with
its specification. Although there are many models in the learnware market, only a few, even none, may be potentially helpful
for the current job. Therefore, how to identify and deploy
useful models becomes one of the main concerns, which particularly matters when the user’s job involves certain unseen
parts not covered by the current learnware market. It becomes
more challenging because, due to the privacy consideration,
the raw data used for training models in the learnware market
are inaccessible. In this paper, we develop a novel schemethat works can effectively reuse the learnwares even when
the user’s job involves unseen parts. Despite the raw training
data are inaccessible, our approach can provably identify samples from the unseen parts while assigning the rest to proper
models in the market for predicting under a certain condition.
Empirical studies also validate the efficacy of our approach.

Learnware Market

Uploading Stage

learnware C: (𝑓𝑓𝐶𝐶 , 𝜇𝜇�𝐶𝐶 )specification

requirement“our”≤ 1.2

email

developers

user

Figure 1: The learnware framework

data, a develop can build a learnware and upload it to themarket for sharing. The second part of participants is theusers who hope to reuse the uploaded learnwares. Whendealing with her own job, a user can search over the market,
identify useful learnwares whose specifications matches therequirements, and then use her data to adapt/polish theselearnwares for her job. The main focus here is how to design
an effective protocol between developers and users, guiding
the development and deployment of learnwares. The desiredlearnware should satisfy several properties (Zhou 2016).
Reusability is one of the core requirements concerningwhich and how the pre-trained models in the market can bereused. Although there are various models, the potentially
useful ones could be few, even non-existent. Thus, it is important to identify which models are helpful for the user’s
current job. Meanwhile, as we cannot expect that there exists
a model trained exactly for the current job, the identified models could only be partially helpful. Even worse, the current
job might contain an unseen part, which is intractable to allexisting models. Thus, how to fully exploit reusable models
while leaving the intractable parts for post-processing is alsoa crucial problem. In addition, we hope the raw data are inaccessible to the user, which ensures developers can share theirexperience safely and avoid data privacy violations.
In this paper, we consider the reusability of learnware in
the scenario where the user hopes to exploit the market topredict her current job directly. This problem is of interest

when the user’s training data are too scarce to support modeltraining. Meanwhile, suppose the user has a label budget. In
that case, the scheme can also be served as a preprocessing for
identifying tractable samples while leaving the rest for label
annotation, where the labeling efficiency can be improved.
It is challenging to ensure reusability and inaccessibilityof raw data simultaneously, as the pre-trained model itself
might not be informative enough to support reusability while
raw data are inaccessible. The pioneering work (Wu et al.
2020) attempts to reuse models via their proposed reduced
kernel mean embedding (RKME) specification. This method
works effectively when the user’s job covered well by thelearnware market, whereas it remains a challenge to handle
scenarios where the user’s job involves unseen parts, which
often occurs particularly when the learnware market is stillin developing. In this paper, we designs a novel deploying
approach to reuse models with RKME specification. Our
method can provably identify samples from unseen parts ofthe current job and assign the rest to proper usable models,
which provides answers to the “which” and “how” problems.
To facilitate an effective approach, we integrate several
techniques from weakly supervised learning (Zhou 2018)with the RKME specification. Specifically, by tailoring the
mixture proportion estimation technique (Ramaswamy, Scott,and Tewari 2016), we answer the problem of “which” byestimating the proportion of each uploaded job and the unseen part in the current job. Then, with the ratios, the risk
rewriting technique (du Plessis, Niu, and Sugiyama 2014;
Zhang et al. 2020) is used to train a job selector, which candirectly identify samples from the unseen part and assign
the rest to proper models. This addresses the “how” problem.
Our method is theoretically supported by the convergence
analysis of the mixture proportion estimator and generalization error analysis for the job selector. We also validate theeffectiveness of our proposal by extensive experiments.

2

Preliminary

This section reviews the RKME specification, and related
techniques, including KME and reduced set construction.
Kernel Mean Embedding. KME (Smola et al. 2007) makes
a powerful representation for a probability distribution. The
idea is to map a probability distribution to a reproducing kernel Hilbert space (RKHS), by representing each distribution
P defined over X as a mean functionZµP :=k(x, ·) dP (x),X

where k : X × X → R is a symmetric and positive definite
kernel function (Schölkopf and Smola 2002), with associated
RKHS H and feature map φ : X → H.
pThe embedding µP
exists and belongs to H, when Ex∼P [ k(x, x)] < ∞.
KME enjoys several favorable properties and is potentiallya nice choice for the specification. First of all, KME makes
a good representation of the distribution, as it can capture
all information about the distribution when using the characteristic kernels such as the Gaussian kernel (Sriperumbudur,
Fukumizu, and Lanckriet 2011). Meanwhile, several elementary operations on distribution can be easily performed with

KME. For example, we can calculate the mean of any function f ∈ H over distribution P directly by the reproducing
property, i.e., EP [f (x)] = hf, µP i for all f ∈ H. These excellent properties encourage KME’s applications in various
distribution related tasks (Gretton et al. 2012; Muandet andSchölkopf 2013; Doran 2013). For more about KME, werefer readers to the fantastic survey (Muandet et al. 2017).
In practice, we can only observe a dataset D = {xn }Nn=1
sampled i.i.d. from the underlying distribution P . Thus, theempirical KME µ
bP is calculated on the dataset to approximate the expected version µP as
1 XN
µ
bP =
k(xn , ·).
n=1
N
As shown by Smola et al. (2007), thebP√ empirical KME µ
converges to µP in the rate of O(1/ N ) measured by the
RKHS norm k · kH under mild conditions.
Reduced Kernel Mean Embedding. Although enjoying
several nice properties, KME requires accessing to raw data,
which violates the inaccessibility of learnware and is not avalid specification. To address this issue, Wu et al. (2020)
introduce the reduced KME to approximated the original
KME via the reduced set method. This method is first used to
speed up SVM prediction (Burges 1996) and receives morecomprehensive studies in Schölkopf et al. (1999).
The idea of RKME is to find a reduced set {(βm , zm )}M
m=1
PM
whose KME µ
eP = m=1 βm k(zm , ·) approximates that of
the original data {xn }N
n=1 . This is achieved by solving
2

min
β,z

XM
1 XN
k(xn , ·) −βm k(zm , ·) , (1)
n=1
m=1
N
H

where βm ∈ R is the coefficient and zm ∈ X is the sample of
the reduced set. The above problem is known as the reduced
set construction (Schölkopf et al. 1999), when zi is a newly
constructed sample. Several methods can be used for handlingthe above problem. We defer descriptions in Appendix A.
RKME µeP enjoys a linear convergence rate O(e−M ) toempirical KME µ
bP when H is finite-dimensional (Bach,
Lacoste-Julien, and Obozinski 2012), which makes it a good
approximation of the distribution. Meanwhile, thanks to the
reduced set construction, raw data are inaccessible to users.
Thus, RKME is an effective specification.

3

Problem Setup

This section introduces the problem setup and notations. We
denote joint, conditional, and marginal distributions by subscripts XY , X|Y , and X throughout the paper. The learnware protocol contains uploading and deploying stages.
Uploading Stage. In this stage, developers should uploadwell-performed models with RKMEs for their jobs.
Specifically, suppose there are C developers in the uploading stage. The i-th developer can access to a local datasetii
Di = {(xn , yn )}N
n=1 sampled from DXY , which is the joint
distribution of the i-th job defined over Xi × Yi .
Based on dataset Di , the developer can train a high-qualityimodel fi : Xi → Yi , which performs well over DXY. BePMisides, a RKME µ
ei = m=1 βm · k(zm , ·) is constructed toPNiapproximate the empirical KME µ
bi = 1/Ni · n=1
k(xn , ·)by minimizing (1). The RKME specification µ
ei makes a goodiapproximation for the feature distribution DX
without accessing the raw data. Afterward, she can upload the learnware
pair (fi , µei ) to the market. For simplicity, we assume thesame feature space for all jobs, i.e., Xi = X for all i ∈ [C].
Deploying Stage. In this stage, the user hopes to exploit
learnwares {(fi , µei )}Ci=1 in the market to handle her own job.
Specifically, we consider the scenario where the user hopestto obtain a classifier f to predict her dataset Dte = {xn }Nn=1 ,whose labels are unknown but sampled from the distributionteDXY
defined over X × Y. It is almost impossible to handle
this problem without any assumption since the distributionte
DXY
can be arbitrarily different from those of uploaded jobs.
Recently, Wu et al. (2020) introduce the instance-recurrent
assumption which assumes the user’s job is well covered byteithe learnware market and DX
to be a mixture of DX, i.e.,
XC
te
i
DXY
=
wi · DXY,(2)
i=1

where w ∈ ∆C . It remains challenging to consider the existence of unseen parts in the user’s job, which often happens
particularly when the market is still in developing.
In this paper, we generalize the previous assumption (2) byfurther considering the unseen parts in the user’s job, whichu
are not covered by the market and have the distribution DXY
over X × Yu . Since the user’s data provide no supervision,
Yu is assumed to have a unique class as Yu = {u}. We refer
unseen parts of the user’s job as an unseen job and introduce
the following unseen-job assumption.
Assumption 1 (unseen-job assumption). The distribution oftethe user’s job DXY
is a mixture of those of uploaded jobs
iu
DXY and the unseen job DXY
as
XC
te
i
u
DXY
=
wi DXY+ wu DXY
,
(3)
i=1
PC
where i=1 wi + wu = 1, wi , wu ≥ 0 for all i ∈ [C].
Assumption 1 is a natural generalization of the instancerecurrent assumption of Wu et al. (2020), since (3) recovers (2) when wu = 0. Due to the existence of the unseen job,
our problem becomes much harder to solve and requires a
new deploying approach. We discuss potential directions thatcan further generalize Assumption 1 in Appendix A.

4

Our ApproachThis section describes our approach. The idea is to train
a selector to recognize which job a user’s testing sample
comes from. With a well-performed job selector, we canidentify intractable samples belonging to the unseen job while
assigning the rest to proper uploaded models for predicting,which can thereby address the problems of “which”, and“how” proposed in Section 1. The challenge is how to train
the selector when the unseen job could exist and raw data of
uploaded jobs are inaccessible.

4.1

Desired Job Selector

To train the job selector, we take each job as a superclass,whose label is denoted by i for the i-th job and u for theunseen job. Thus, the selector is essentially a multiclass classifier g(x) : X → I with I = {1, . . . , C, u}. Given a testing sample x, when g(x) ∈ [C], the user can predict it as
f (x) = fg(x) (x) with the g(x)-th uploaded model, otherwise predict that it comes from the unseen job as f (x) = u.
We show that the generalization error of the decision function
f is highly related to the quality of the job selector.
Proposition 1. Under Assumption 1, suppose all uploadedmodels {fi }C
i=1 perform well over their jobs such thati
EDXY
[1(fi (x) 6= y)] ≤  holds for all i ∈ [C]. The generalization error of the prediction function f is bounded by
te [L01 (f (x), y)] ≤  + R(g),
EDXY

(4)

where L01 (f (x), y) = 1[f (x) 6= y] and 1[·] is the indicatorfunction. The risk of job selector R(g) is defined by
XC
i [L01 (g(x), i)] + wu ED u [L01 (g(x), u)] (5)wi EDX
X
i=1

Proposition 1 implies that once the selector g minimizes
R(g), we can obtain a high-quality decision function by exploiting the uploaded models. We note that minimizing (5)is the key to address the “which” and “how” problems, as
the mixture proportions {wi }C
i=1 indicate which models areuseful and the selector tells how to use them. Unfortunately,
the 0-1 loss L01 is non-convex, which makes the risk minimization problem generally intractable.
The common practice to handle this problem is to use aconvex surrogate loss function to substitute the 0-1 loss. In
the multiclass scenario, instead of training a single classifier g
directly, we usually train multiple binary classifiers gi : X →R for each i ∈ I to distinguish the i-th class from others,
and then predict as g(x) = arg maxi∈I gi (x). Denoting by
g(x) = [g1 (x), . . . , gC (x), gu (x)] the vector function, we
can train the binary classifiers by minimizing the expectedrisk RΨ (g) w.r.t. a convex surrogate loss defined by
XC
i [LΨ (g(x), i)] + wu ED u [LΨ (g(x), u)] (6)wi EDX
X
i=1

There are multiple choices for the multiclass surrogate lossLΨ : RC+2 → R (Zhang 2004), such as the one-versus-rest(OVR) and pairwise comparison (PC) losses. The consistency
between functions minimizing RΨ (g) and that minimizingRΨ (g) is also studied in the seminal work of Zhang (2004).
To minimize the expected risk RΨ (g), it requires knowing
i
u
i
DX
, DX
, {wi }C
i=1 and wu . The feature distribution DX canbe approximated directly by the RKMEs µ
ei . However, theuestimation of DX
is challenging since the unseen job has
never been uploaded in the learnware market. In the nextpart, we present the method to minimize RΨ with only the
RKMEs {eµi }Ci=1 and user’s testing data, assuming that the
mixture proportions {wi }C
i=1 , wu were known, for a moment.

4.2

Expected Risk Rewriting

One of the main challenges to minimize RΨ (g) is that thelearnware market cannot provide any information about theumarginal distribution of unseen job DX. We handle this problem by using the risk rewriting technique (du Plessis, Niu,
and Sugiyama 2014; Zhang et al. 2020) with the user’s unlabeled data. The intuition is that though the unseen job isunever uploaded, its marginal distribution DX
is hidden in theuser’s testing data. Under Assumption 1, summing over theulabel set, we can estimate DX
by separating the distributionsof uploaded job from that of the unlabeled data as
u
te
DX
= DX
−

XC
i=1


i
wi DX
/wu .

(7)

Rewriting (6) with (7), we have the following proposition.
Proposition 2. Under Assumption 1, for all measurable function gi : X → R with i ∈ I, we haveRΨ (g) =XC
i=1i [LΨ (g(x), i) − LΨ (g(x), u)]
wi EDXte [LΨ (g(x), u)].
+ EDX

(8)

Proposition 2 show that RΨ (g) is only established on theidistribution of uploaded jobs DX
and that of the user’s datate
DX . Thus, we can train the selector by minimizing its empirbΨ (g), where the distributions Di and Dte areical version R
X
X
approximated with their empirical observations Di and Dte .
However, raw data Di are inaccessible and the only available resource is the associated RKME. To address this problem, we employ the kernel herding technique (Chen, Welling,
and Smola 2010; Bach, Lacoste-Julien, and Obozinski 2012)
e i = {xi }Nei from the RKME
to sample a mimic dataset D
n=1bΨ (g) becomesµei to substitute Di , where the empirical risk RbΨ (g) =R

wi X(LΨ (g(xn ), i) − LΨ (g(xn ), u))
i=1 N
ei

XC

ei
x n ∈D+

1Nt

X

Lψ (g(xn ), u).

(9)xn ∈Dtee i provides a suffiIn Section 5, we theoretically justify that D
cient approximation for training the selector.
bΨ (g) is generally non-convex, makThe last issue is that R
ing it hard to optimize. We can eliminate the non-convexity
by choosing proper multi-class surrogate losses LΨ and innerbinary losses ψ. In this paper, We use the OVR lossX
LOVR
ψ(−gj (x)),Ψ (g(x), i) = ψ(gi (x)) +j6=iwith the convex binary loss ψ : R → R satisfying ψ(z) −ψ(−z) = −z, for all z ∈ R (du Plessis, Niu, and SugiyamabΨ (g) is convex w.r.t. g and can be2015).1 In such a case, R
optimized efficiently. Practically, we train the selector bybΨ (g)
e = arg ming1 ,...,gC ,gu ∈G R
g

(10)

where G = {g ∈ H | kgkH ≤ BG } is a RKHS-based hypothesis set. We present more descriptions for kernel herdingbΨ (g) in Appendix A.
and the convex formulation of R
1

Many loss functions satisfy the condition, such as logistic loss
ψ(z) = log(1 + exp(−z)), square loss ψ(z) = (1 − z)2 /4 anddouble hinge loss ψ(z) = max(−z, max(0, (1 − z)/2))

4.3

Mixture Proportion Estimation with RKMEThis part shows how to estimate {wi }C
i=1 and {wu } with
RKMEs and user’s unlabeled data.
No Unseen Job. The problem is straightforward suppose we
knew there is no unseen job. By summing (2) over the labelPCteiset Y, we have DX= i=1 wi DX. Since the RKME µ
ei is ai
good approximation of the marginal distribution DX, we use
the relationship among KMEs to solve {wi }C
i=1 by
2
XC
(11)
min
wi µ
ei − µ
bte
,
w∈∆

i=1

H

where w = [w1 , · · · , wC ]T and ∆C is the probability simPNt
plex. Notation µbte = 1/Nt · n=1
k(xn , ·) is the empirical
KME of the testing data. Note that (11) can be solved by aquadratic program (Smola et al. 2007).
The above method is infeasible in our setting due to the unseen job’s absence. Our idea is to estimate individual mixturePC
proportion wi and then calculate wu = 1 − i=1 wi .
MPE Problem. The estimation of individual wi can be castas a mixture proportion estimation (MPE) problem (Blanchard, Lee, and Scott 2010; Jain et al. 2016; du Plessis, Niu,
and Sugiyama 2017). In the MPE problem, the user observes
Nf
two datasets, DF = {xn }n=1sampled i.i.d. from distribuhtion F and DH = {xn }Nsampledi.i.d from H, wheren=1
F = wH + (1 − w)G is a mixture of H and an unobserved
distribution G with proportion w ∈ [0, 1]. The goal of theuser is to estimate w with the empirical data DF and DH .
te
Clearly, in our scenario, we can take F = DX
andi
H = DX , and use Dte and Di to estimate wi with developed
estimators. Nevertheless, the raw training data Di are inaccessible, which limits the application of most existing MPE
estimators as they always require the raw data. To handle thisproblem, we tailor the KME based estimator (Ramaswamy,
Scott, and Tewari 2016) to fit the RKME specification.
Expected KME Estimator. MPE problem is generally illdefined unless we impose certain assumptions. In literature,
the irreducible assumption and its variants (Blanchard, Lee,and Scott 2010; Scott 2015) are proposed to ensure a uniquevalue of the true mixture proportion wi . Furthermore, Blanchard, Lee, and Scott (2010) have observed that the true wiiteis identical to the maximum proportion of DX
in DX
when
the irreducible assumption holds.
Based on the observation, we can identify wi by the maxteiimum wbi that makes G0 = (DX−wbi DX)/(1 − wbi ) still avalid distribution. That is, if the estimated mixture proportionw
bi is greater than the true one wi , the density function of G0
would go negative, making it an illegal distribution. The problem here is how to judge whether G0 is a valid distribution?
The above problem can be handled with KME. For simplicity, we rewrite the mixture proportion as λi = 1/(1−wi ) andbi = 1/(1 − w
λbi ), where λi ∈ [1, +∞) is monotonically inbi Dte + (1 − λbi )Di .
creasing w.r.t. wi . In such a case, G0 = λXX0One can define the distance from G to a set containing all
valid distributions asbi ) = inf λbi µte + (1 − λbi )µi −h ,
d(λ
H
h∈C |
{z
}
µG0

where C = {h ∈ H | h = µQ for some distribution Q} isbi ≤ λi , G0 is
the set of KMEs of all valid distributions. If λbbi ) > 0.
a valid distribution, then d(λi ) = 0, otherwise d(λbi ) is non-decreasing andMoreover, the distance function d(λconvex over [1, +∞). Thus, we can use binary search tobi making d(λbi ) > 0. Moreidentify λi as the critical value λillustration of the idea and formal descriptions of the properb with their proofs can be found in Appendix B.
ties of d(λ)
Empirical RKME Estimators. In the deploying phase, webi ) empirically by
can approximate d(λbλbi ) = inf λ
bi µ
bi )e
d(
bte + (1 − λµi − h
h∈Cb

H

,

(12)

where µbte is the empirical KME of the testing data and µ
ei is
the RKME for the i-th job. The set Cb = {h ∈ H | h =
PNt
PMi
PNt
an k(xn , ·) + bm m=1
k(zm , ·), for n=1
an +
n=1
PMi
m=1 bm = 1} contains all empirical KMEs establishedMitover {xn }N
n=1 and {zm }m=1 . We can calculate the value of2bλbi )) by solving a quadratic program.
(d(bλbi ) does not enjoy the nice propThe empirical distance d(bi ), as it could be greater than 0, even whenerties as d(λbλi < λi . However, it is still non-decreasing and convex overbi ) with the growth of Nt and[1, +∞) and converges to d(λMi . We can specify a threshold ν rather than 0 to identify thetrue weight. Formally speaking, we can estimate λi bybV = inf{λbi : d(bλbi ) > ν}.
λ
i

(13)

bλ
bi ) is convex over [1, +∞), its gradient
Besides, since d(is non-decreasing over [1, +∞) and thus thresholding thegradient is also a viable strategy. We can estimate λi bybG = inf{λbi : ∃g 0 ∈ ∂ d(bλbi ), g 0 ≥ ν}.
λi

A Summary of Deploying Approach

Finally, we summarize our deploying approach, where wefirst estimate the mixture proportion wi by the estimatorPCwbiG and calculate w
buG = 1 − i=1 w
biG , followed by theselector training via (10). Then, we use the selector ge(x) =arg mini∈I gei (x) to identify samples from the unseen job
and assign the rest to proper models for predicting. Detailed
implementations of the MPE estimator (Algorithm 1) andselector training (Algorithm 2) are provided in Appendix A.

5Theoretical Analysis

In this section, we theoretically justify our method by providing the excess risk bound for the selector and convergence
analysis for the RKME based MPE estimator.

Excess Risk Bound for Job Selector

We first provide the excess risk bound for our selector trainedwith the true mixture proportions. The convergence analysis
for the MPE estimator is shown in the next subsection. For
simplicity, we further assume Mi = M and Ni = N for all
e i | is greater than M asi ∈ [C] and the size of mimic data |D
we can generate an arbitrary number of mimic data.
Theorem 1. Suppose k(x, x) ≤ 1 holds for all x ∈ X andbinary loss ψ satisfies Bψ ≥ 0 and is L-Lipschitz.2 Then,
1
1
−1
RΨ (e
g) − RΨ (g∗ ) ≤ O (C + 1)(N − 2 + Nt 2 ) + M − 2holds for all g1 , . . . , gC , gu ∈ G. The optimal classifier g∗ =arg ming1 ,...,gC ,gu ∈G RΨ (g) minimizes the expected risk RΨover the hypothesis space G.
Theorem 1 essentially states that despite the inaccessibilityof the raw data and the existence of the unseen job, our job
selector converges to the optimal one trained over the testing
distribution. We defer the detailed proof to Appendix B.
Remark 1. The proof of Theorem 1 is established on the cornerstone that RKME
ei converges to the empircal KME µ
bi in
√ µ
the rate of O(1/ M ). We note that this rate can be improvedto O(e−M ) when the RKHS is finite-dimensional (proofs areshown in Appendix B). This rate indicates that with a tinye√reduced set M = O(log N ), our selector gconverges to the√∗
optimal one g in the rate of O((C + 1)(1/ N + 1/ Nt )),which is the standard rate for the empirical risk minimization method trained with raw data, which further validates
the effectiveness of the RKME specification. Although in
the infinite-dimensionalsetting, the current theory only sup√ports the O(1/ M ) rate, our experiments show that a tiny
reduce set (M = 10 vs N = 2500) is sufficient to support
satisfactory empirical performance.

5.2
(14)

bG achieves better performance.
Empirical studies show that λiThus, we use it for our mixture proportion estimator. AfterbG , we calculate w
bG − 1)/λbG .
estimating λbiG = (λ
i
i
i

4.4

5.1

Convergence Analysis for MPE Estimator

As we have mentioned, the MPE problem is not well defined
unless we introduce certain assumptions. For analyzing the
RKME based estimator, we require the separability assumption introduced by Ramaswamy, Scott, and Tewari (2016).
Assumption 2 (separability assumption). A kernel k anddistributions G, H satisfy the separability condition with
margin α > 0 and tolerance β, if ∃h ∈ H, khkH < 1 andEx∼G [h(x)] ≤ inf h(x) + β ≤ Ex∼H [h(x)] − α.
xThe separability assumption states that H and G are separated enough evaluated by a function space, which is a naturalextension of the assumption supp(H) * supp(G) to the function space setting (Ramaswamy, Scott, and Tewari 2016). In
i
i :=
te
i
our case, H = DX
and G = D̄X(DX−wi DX)/(1−wi )teiis the rest distribution in DX apart from DX . The two distributions are separable in applications as they are the marginal distribution for different jobs. We provide the convergence ratebG , whose proofs are deferred to Appendix B.
for estimator λi2Common surrogate loss functions satisfy these conditions, suchas logistic loss, exp loss and square loss.

/
/
/

Job 1
Job 2
Job 3

(a) Uploaded jobs

Job 1
Job 2
Job 3

Testing data(b) RKMEs(a) Current job

Figure 2: Uploading phase
Theorem 2. Suppose k(x, x) ≤ 1 holds for all x ∈ X . Letiikernel k and distribution DX, D̄X
satisfy the separability
condition with margin α > 0 and tolerance
β. Let ν ∈
√
h
i p
192
log(1/δ)α3αbmin{N, M, Nt } ≥ α/λi −ν and µei ∈ C.
4λi , 4λi ,With probability at least 1 − 4δ, we havebG ≤ O((min{N, M, Nt })−1/2 )λi − λibG − λi ≤ 8βλi /α + O((min{N, M, Nt })−1/2 ).
λi
The convergence rate of MPE estimator is similar withthe excess risk bound of job selector, whose dependence
on M can also be improved to O(e−M ) when H is finitedimensional. Theorem 1 together with Theorem 2 show that
our approach can provably train a well-performed job selector,
even when the unseen job exists and raw data are unavailable.

6

Related Work and Discussion

In this section, we discuss related works from two aspects.
Related Topics. Domain adaptation (Ben-David et al. 2006)
and transfer learning (Pan and Yang 2010) aim to adapt
source data to help the training on target data. The problem is that the raw source data are available when training
the target model, which is not applicable in the learnware
scenario. More relevant topics to ours are learning from auxiliary classifiers (Duan et al. 2009) or hypothesis transfer
learning (Kuzborskij and Orabona 2013, 2017; Zhao, Cai,and Zhou 2020), where researchers attempt to exploit pretrained models for handling learners’ current jobs. Theirassumption is that the given pre-trained models are always
helpful for the current job, which exhibits striking difference
from our problem as helpful models could be only a few
even non-existent in the learnware market. Multi-party learning (Pathak, Rane, and Raj 2010; Wu, Liu, and Zhou 2019)
also considers uniting local data to solve the same/similar job
in privacy-preserving ways. But they assume that every local
data is relevant to the user’s current job, which is not the casein learnware as the reusability is one of its main concerns.
There are recent efforts devoted to the issue of reusability.
Specifically, Wu et al. (2020) make the first attempt to reusea pool of model with the RKME specification. Later, Ding
and Zhou (2020) use outlier detectors as the specification anddevelop a boosting-based approach to deploy models. The
difference between our work and previous studies is that we
consider the existence of the unseen job, the identification ofwhich requires new deploying algorithms.

//+

Unseen(b) Predictions

Figure 3: Deploying phase

Related Techniques. The main technical stuffs, mixture proportion estimation (Jain et al. 2016; du Plessis, Niu, andSugiyama 2017; Bekker and Davis 2018) and risk rewriting
technique (du Plessis, Niu, and Sugiyama 2014, 2015; Zhang
et al. 2020), have been developed in the research field of
weakly supervised learning. However, all the existing methods rely on the raw data, which are not applicable in the learnware scenario. Our contribution is to modify and integratethem with the RKME specification, where we theoreticallyjustify the compatibility of our modification.

7

Experiments

This section examines the efficacy of our method, where wecompare our method with contenders in various scenarios. In
the following, we first illustrate our method by a toy example,
followed by the comparisons on benchmark datasets.

7.1

Toy Example

Following the empirical studies of Wu et al. (2020), we firstillustrate the RKME based learnware by a toy classification
problem. There are two stages of the toy experiment.
Uploading phase. Figure 2 illustrates the uploading phase.
There are three developers in the market, whose local datasets
are denoted by “ ”, “ ”, “ ”. Each local dataset contains
160 samples and is generated from mixture of different Gaussian distributions. Labels of each dataset are decided by acircle where yellow ones are positive (“+”) while blue ones
are negative (“−”). Based on their training data, developers
construct learnwares individually, where linear models aretrained over the local datasets and RKMEs are built. The
reduced set size is M = 5, equaling bln 160c and is quite
fewer comparing with the raw training data.
Deploying phase. Figure 3 illustrates the deploying phase,where the current job is taken as a mixture of uploaded
jobs and an unseen part (denoted by “ ”). The true mixture proportion of the uploaded jobs is [0.5, 0.2, 0, 0.3] for“ ”, “ ”, “ ” and “ ”. By exploiting the unlabeled testing data and RKMEs of the uploaded jobs, the estimatedproportions returned by our RKME based MPE estimatorare [0.506, 0.182, 0.013, 0.299], which is close to the groundtruth. Figure 3(b) shows the the decision boundary of theselector, which essentially identifies the unseen job samples
and assign the rest to proper models.

Datasets

Job number

Instance-recurrent assumption (2)Unseen-job assumption (3)RKME-basic

Ours

RKME-OCSVM

RKME-iForest

Ours

Ours-oracle

OracleCIFAR-1002
5
1075.90 ± 5.41
75.43 ± 3.92
75.95 ± 2.34

79.28 ± 4.84
72.59 ± 4.80
73.28 ± 2.10

62.81 ± 6.13
49.80 ± 2.73
44.70 ± 2.02

58.55 ± 4.74
37.85 ± 2.64
29.18 ± 2.97

90.32 ± 2.02
76.04 ± 4.84
72.42 ± 3.81

90.39 ± 2.22
79.15 ± 2.01
74.49 ± 2.71

93.55 ± 1.52
87.88 ± 2.77
86.43 ± 1.95

Newsgroup20

23485.75 ± 7.59
88.18 ± 6.69
87.10 ± 6.38

84.31 ± 8.34
86.70 ± 6.79
83.32 ± 6.89

56.44 ± 7.03
52.93 ± 3.81
48.94 ± 2.69

59.01 ± 5.46
48.58 ± 3.59
43.75 ± 3.53

79.91 ± 9.98
75.56 ± 6.39
71.19 ± 6.15

88.73 ± 7.48
83.43 ± 4.21
80.90 ± 2.50

93.64 ± 4.94
90.55 ± 3.61
89.88 ± 2.09

ELT Character23
487.47 ± 5.04
87.09 ± 2.35
86.23 ± 2.63

88.15 ± 4.26
84.15 ± 3.28
81.45 ± 2.93

31.56 ± 7.56
37.79 ± 9.05
44.75 ± 4.59

38.15 ± 12.8
37.27 ± 10.0
39.49 ± 6.55

91.85 ± 2.63
85.52 ± 5.30
76.01 ± 5.53

93.14 ± 2.06
88.85 ± 4.40
84.61 ± 2.97

95.67 ± 2.74
95.49 ± 1.61
94.10 ± 1.67

Table 1: Accuracy on true labels. The best feasible method is emphasized in bold (paired t-tests at 5% significance level).

7.2

Benchmark Datasets

We evaluate our method on benchmark datasets to show its effectiveness on reusing models. As the reusability of a pool ofmodels is a new problem, we first compare with the baseline.
• RKME-basic (Wu et al. 2020) exploits the RKME toreuse the model pool under the instance-recurrent assumption (2), where the existence of unseen job is not considered. We take this method as a baseline.
To evaluate how well our method can perform, we comparewith two skylines, which is not feasible in real applications.
• Oracle knows the job each sample belongs to. It enjoys
the best performance that the pool of models can achieve.
• Ours-oracle uses our method to train the selector withtrue {wi }C
i=1 , served a skyline for the MPE estimator.
Meanwhile, since RKME-basic method cannot identify theunseen job, we equip it with novelty detectors, which can beseen as another specification provided by the developer.
• RKME-OCSVM equips RKME-basic with the one-classSVM (Schölkopf et al. 2001), where an OCSVM is provided for each uploaded job as an additional specification.
When a sample is rejected by all one-class SVMs of the
uploaded jobs, it is predicted as from the unseen job. The
rest samples are predicted with RKME-basic.
• RKME-iForest equips RKME-basic with iForest (Liu, Ting, and Zhou 2008) to predict the unseen job.
For all RKHS based methods, we exploit the Gaussian
kernel k(x, y) = exp(−γkx − yk22 ) with γ = 0.01. The
reduced set size is M = 10 which is very tiny size. As
for our method, we set ν = 0.25 for the MPE estimator andchoose the square loss ψ(z) = (1 − z)2 /4 for the job selector.
Datasets. The evaluation is conducted on three widely usedbenchmark datasets: CIFAR-100 (Krizhevsky 2009), Newsgroup20 (Joachims 1997) and an ETL character dataset.
CIFAR-100 has 100 classes and are naturally divided into
20 parts and each has 5 classes. We simulate the learnware
scenario by taking each part as a job, which contains 2500
training instances. Newsgroup20 has a similar configuration,
where there are 5 jobs and each has 2000 instances. The character dataset consists of characters from 6 different scripts.
Each script is seen as a job and has at least 6528 instances.
Configuration. To evaluate the method, we compare itwith contenders in various scenarios. First, we compare to
RKME-basic under the instance-recurrent assumption (2),where no unseen job appears. RKME-basic is specificallydesigned for this scenario. The goal of the comparison is toevaluate the safety of our method even if it always assumes
the existence of potential unseen jobs. Next, we conduct experiments with emerging unseen jobs, where only parts oflocal jobs are uploaded, and there is always one unseen job.
In both scenarios, the current job is stimulated by randomly
mixing a different number of local jobs with equal mixture
proportions. All experiments are repeated 10 times.
More detailed descriptions for contenders, datasets, andexperimental configurations can be founded in Appendix C.
Results. Table 1 presents the prediction accuracy over thetrue label of the testing data, where the unseen job is assumed to have a unique class. We provide more evaluationon other measures in Appendix C. As shown in the comparison under the instance-recurrent assumption (2), our method
achieves comparable performance with RKME-basic in various numbers of mixed jobs, which shows that our method issafe to use when there is no unseen job. The comparison under the unseen-job assumption (3) validates the superiority of
our method. The novel detectors do not achieve the expected
performance. The reason might be that it is solely trained
over the local dataset, whose predictions on other jobs might
not be accurate. On the contrary, by exploiting the unlabeled
testing data, our method can align binary classifiers in the
OVR scheme to select the job a testing sample comes from.
The comparison between Ours and Ours-oracle
shows the MPE estimator is accurate, as Ours-oracle
is trained with the true {wi }C
i=1 , while our method achieves
comparable performance in most cases. The comparison between Ours-oracle and Oracle further validates ourjob selector’s efficacy, as Ours-oracle trains the selector
with only a tiny reduced set size M = 10 while Oracle isassumed to know each sample’s ground truth job.

8

Conclusion

This paper attempts to address the challenge of how to reuselearnwares when the user’s job involves unseen parts not covered by the current learnware market. Based on the recently
proposed RKME specification and advances in weakly supervised learning, we design a provably effective approachthat can identify the unseen job samples while assigning therest to proper models. Empirical evaluation validates that ourapproach can be safely applied no matter whether there areunseen jobs or not. An interesting future issue is to consider
the labeling cost budget.

References
Bach, F. R.; Lacoste-Julien, S.; and Obozinski, G. 2012. On
the equivalence between herding and conditional gradientalgorithms. In Proceedings of the 29th International Conference on Machine Learning (ICML), 1355–1362.
Bekker, J.; and Davis, J. 2018. Estimating the class prior inpositive and unlabeled data through decision tree induction.
In Proceedings of the 22nd AAAI Conference on Artificial
Intelligence (AAAI), 2712–2719.
Ben-David, S.; Blitzer, J.; Crammer, K.; and Pereira, F.
2006. Analysis of representations for domain adaptation.
In Advances in Neural Information Processing Systems 19(NeurIPS), 137–144.
Blanchard, G.; Lee, G.; and Scott, C. 2010. Semi-supervised
novelty detection. Journal of Machine Learning Research
11: 2973–3009.

Krizhevsky, A. 2009. Learning multiple layers of featuresfrom tiny images. Technical Report .
Kuzborskij, I.; and Orabona, F. 2013. Stability and hypothesis
transfer learning. In Proceedings of the 30th International
Conference on Machine Learning (ICML), 942–950.
Kuzborskij, I.; and Orabona, F. 2017. Fast rates by transferring from auxiliary hypotheses. Machine Learning 106(2):171–195.
Liu, F. T.; Ting, K. M.; and Zhou, Z.-H. 2008. Isolation forest.
In Proceedings of the 8th IEEE International Conference on
Data Mining (ICDM), 413–422.
Muandet, K.; Fukumizu, K.; Sriperumbudur, B. K.; andSchölkopf, B. 2017. Kernel mean embedding of distributions: A review and beyond. Foundations and Trends in
Machine Learning 10(1-2): 1–141.

Burges, C. J. C. 1996. Simplified support vector decisionrules. In Proceedings of the 13th International Conference
on Machine Learning (ICML), 71–77.

Muandet, K.; and Schölkopf, B. 2013. One-class support
measure machines for group anomaly detection. In Proceedings of the 29th Conference on Uncertainty in Artificial
Intelligence (UAI), 449–458.

Chen, Y.; Welling, M.; and Smola, A. J. 2010. Super-samples
from kernel herding. In Proceedings of the 26th Conference
on Uncertainty in Artificial Intelligence (UAI), 109–116.

Pan, S. J.; and Yang, Q. 2010. A survey on transfer learning.
IEEE Transactions on Knowledge and Data Engineering
22(10): 1345–1359.

Ding, Y.-X.; and Zhou, Z.-H. 2020. Boosting-based reliable
model reuse. In Proceedings of the 12th Asian Conference
on Machine Learning (ACML), 145–160.

Pathak, M. A.; Rane, S.; and Raj, B. 2010. Multiparty differential privacy via aggregation of locally trained classifiers.
In Advances in Neural Information Processing Systems 23(NeurIPS), 1876–1884.

Doran, G. 2013. Distribution kernel methods for multipleinstance learning. In Proceedings of the 27th AAAI Conference on Artificial Intelligence (AAAI), 1660–1661.
du Plessis, M. C.; Niu, G.; and Sugiyama, M. 2014. Analysisof learning from positive and unlabeled data. In Advances in
Neural Information Processing Systems 27 (NeurIPS), 703–
711.
du Plessis, M. C.; Niu, G.; and Sugiyama, M. 2015. Convex formulation for learning from positive and unlabeled
Data. In Proceedings of the 32nd International Conference
on Machine Learning (ICML), 1386–1394.
du Plessis, M. C.; Niu, G.; and Sugiyama, M. 2017. Classprior estimation for learning from positive and unlabeled data.
Machine Learning 463–492.
Duan, L.; Tsang, I. W.; Xu, D.; and Chua, T. 2009. Domain
adaptation from multiple sources via auxiliary classifiers. In
Proceedings of the 26th Annual International Conference on
Machine Learning (ICML), 289–296.
Gretton, A.; Borgwardt, K. M.; Rasch, M. J.; Schölkopf, B.;
and Smola, A. J. 2012. A kernel two-sample test. Journal of
Machine Learning Research 13: 723–773.

Ramaswamy, H. G.; Scott, C.; and Tewari, A. 2016. Mixture
proportion estimation via kernel embeddings of distributions.
In Proceedings of the 33rd International Conference on Machine Learning (ICML), 2052–2060.
Schölkopf, B.; Mika, S.; Burges, C. J. C.; Knirsch, P.; Müller,
K.; Rätsch, G.; and Smola, A. J. 1999. Input space versus
feature space in kernel-based methods. IEEE Transactions
on Neural Networks 10(5): 1000–1017.
Schölkopf, B.; Platt, J. C.; Shawe-Taylor, J.; Smola, A. J.;
and Williamson, R. C. 2001. Estimating the support of ahigh-dimensional distribution. Neural Computation 13(7):1443–1471.
Schölkopf, B.; and Smola, A. J. 2002. Learning with kernels:
Support vector machines, regularization, optimization, andbeyond. Adaptive Computation and Machine Learning Series.
The MIT Press.
Scott, C. 2015. A rate of convergence for mixture proportion
estimation, with application to learning from noisy labels. In
Proceedings of the 18th International Conference on Artificial Intelligence and Statistics (AISTATS), 838–846.

Jain, S.; White, M.; Trosset, M. W.; and Radivojac, P. 2016.
Nonparametric semi-supervised learning of class proportions
arXiv:1601.01944.

Smola, A. J.; Gretton, A.; Song, L.; and Schölkopf, B. 2007.
A Hilbert space embedding for distributions. In Proceedings of the 18th International Conference on Algorithmic
Learning Theory (ALT), 13–31.

Joachims, T. 1997. A probabilistic analysis of the Rocchio
algorithm with TFIDF for text categorization. In Proceedingsof the 14th International Conference on Machine Learning(ICML), 143–151.

Sriperumbudur, B. K.; Fukumizu, K.; and Lanckriet, G. R. G.
2011. Universality, characteristic kernels and RKHS embedding of measures. Journal of Machine Learning Research 12:
2389–2410.

Wu, X.-Z.; Liu, S.; and Zhou, Z. 2019. Heterogeneous model
reuse via optimizing multiparty multiclass margin. In Proceedings of the 36th International Conference on Machine
Learning (ICML), 6840–6849.
Wu, X.-Z.; Xu, W.; Liu, S.; and Zhou, Z.-H. 2020. Model
reuse with reduced kernel mean embedding specification
arXiv:2001.07135.
Zhang, T. 2004. Statistical analysis of some multi-category
large margin classification methods. Journal of Machine
Learning Research 5: 1225–1251.
Zhang, Y.-J.; Zhao, P.; Ma, L.; and Zhou, Z.-H. 2020. An
unbiased risk estimator for learning with augmented classes.
In Advances in Neural Information Processing Systems 33(NeurIPS), to appear.
Zhao, P.; Cai, L.-W.; and Zhou, Z.-H. 2020. Handling concept
drift via model reuse. Machine Learning 109(3): 533–568.
Zhou, Z.-H. 2016. Learnware: On the future of machinelearning. Frontiers of Computer Science 10(4): 589–590.
Zhou, Z.-H. 2018. A brief introduction to weakly supervised
learning. National Science Review 5(1): 44–53.