# Learning from Positive and Unlabeled Data with Augmented Classes

Zhongnian Li1, Liutao Yang2, Zhongchen Ma3, Tongfeng Sun1, Xinzheng Xu1 and
Daoqiang Zhang2
1Department of Computer Science, China University of Ming and Technogy
2Department of Computer Science, Nanjing University of Aeronautics and
Astronautics
3Department of Computer Science, Jiangsu University
<EMAIL_ADDRESS><EMAIL_ADDRESS>
Corresponding author

###### Abstract

Positive Unlabeled (PU) learning aims to learn a binary classifier from only
positive and unlabeled data, which is utilized in many real-world scenarios.
However, existing PU learning algorithms cannot deal with the real-world
challenge in an open and changing scenario, where examples from unobserved
augmented classes may emerge in the testing phase. In this paper, we propose
an unbiased risk estimator for PU learning with Augmented Classes (PUAC) by
utilizing unlabeled data from the augmented classes distribution, which can be
easily collected in many real-world scenarios. Besides, we derive the
estimation error bound for the proposed estimator, which provides a
theoretical guarantee for its convergence to the optimal solution. Experiments
on multiple realistic datasets demonstrate the effectiveness of proposed
approach.

##  1 Introduction

Learning from Positive and Unlabeled (PU)Bekker and Davis (2020); Niu et al.
(2016); du Plessis et al. (2014); Bekker et al. (2019); du Plessis et al.
(2015) data is a type of weakly supervised learningLu et al. (2019); Ishida et
al. (2018); Bao et al. (2018); Shimada et al. (2021), which has drawn
considerable attention in many real-world scenarios. The goal of PU learning
is to train a binary classifier by using only positive and unlabeled data
without the assistance of negative label, which requires huge costs in some
tasks. PU learning has many practical applications, such as, text
classification, image annotation, time series categorization, bio-medicine
analysis and so on.

Previous researchesGuo et al. (2020b); Sansone et al. (2019); Sakai and
Shimizu (2019); Kato et al. (2019) focus on handling unlabeled data to solve
the PU learning problem. Specifically, a line of effective algorithms aim to
extract possible negative examples from unlabeled dataLi and Liu (2003);
Mordelet and Vert (2014), and then train a binary classifier. The performance
of this category is heuristic and strongly influenced by selected negative
examples. Another category methods train PU learning classifiers by treating
unlabeled data as noise negative examples. Thus, the classifier can be trained
by utilizing the small weights for negative datadu Plessis et al. (2014,
2015), which heavily relies on the choice of weight for unlabeled data.

However, it is noteworthy that exist studies on PU learning were in a stable
scenario rather than non-stationary environmentWei et al. (2021); Pham et al.
(2015); Guo et al. (2020a), where some examples derived from unobserved
classes in training phase might emerge in the testing dataZhang et al. (2020);
Da et al. (2014). In this paper, we focus on PU learning with Augmented
Classes (PUAC). Augmented classes classification desire to make reliable
prediction, which not only identifies augmented classes but also classifies
the data form observed classes accurately in testing phase.

Figure 1: One example of Positive and Unlabeled data with Augmented Classes.
The augmented class (Tiger) only appear in testing dataset, which is not
observed in positive and unlabeled data.

For example, in the task of felidae image annotation utilizing PU learning in
the Internet, the user may only label cat images as positive data and the
absence label images as unlabeled data as shown in Fig.1. In the traditional
PU learning setting, unlabeled data only consist of cat and non-felidae
images. However, since the environment is open and change, there may appear
some images from augmented classes, such as tiger images. When an image of
tiger comes, exist PU classifiers nearly predict it in the cat or non-felidae
class, which will degrade performance of those classifiers. When facing some
open and change scenarios in the real world, a mature PU learning algorithm
need to work in PUAC setting.

In order to deal with the PUAC problem, we propose an unbiased risk estimator
called UPUAC, short for Unbiased risk estimator of Positive and Unlabeled
learning with Augmented Classes. UPUAC exploits unlabeled data form the
augmented classes distribution, which can be collected easily from many real-
world scenarios. More concretely, we rewrite the risk into an equivalent
expression by utilizing positive, unlabeled and augmented classes
distributions, which will lead to an unbiased risk estimators for PUAC.
Besides, we provide a theoretical analysis of estimation error bound which
certainly guarantees the estimator converges to the optimal solution.
Experimentally, by comparing with existing state-of-the-art PU learning
approach, our UPUAC achieves the best classification performance when the
augmented classes emerges on multiple realistic datasets. Beyond that, we test
proposed UPUAC with some inaccurate class priors, which may be obtain by
mixture proportion estimationdu Plessis et al. (2017); Ramaswamy et al.
(2016).

##  2 Preliminaries

In this section, we describe PUAC problem setting and review notations of risk
rewrite briefly.

###  2.1 Problem Setting of PUAC Learning

In traditional PU learning, the learner collects two datasets
$D_{p}=\\{{x}_{i}^{p}\\}_{i=1}^{n_{p}}$ and
$D_{u}=\\{{x}_{i}^{u}\\}_{i=1}^{n_{u}}$ sampled from positive distribution
$P_{p}(x)$ and unlabeled distribution $P_{u}(x)$ respectively, where ${\bf
x}\in\mathbb{R}^{d}$ is a $d$-dimensional feature and $\mathcal{X}$ is the
feature space. Let $y_{i}\in\\{p,n\\}$ denotes the class label and
$\mathcal{Y^{\prime}}=\\{p,n\\}$ denotes the label space for traditional PU
learning. In the PUAC problem, the learner requires to train a classifier by
using the data form the augmented classes distribution, where data from
unobserved augmented classes might emerge. Since the number of augmented
classes is unknown, the data generated form unobserved augmented classes will
be predicted as a single class $\bf a$. In our setup, an unlabeled dataset
$D_{a}=\\{{x}_{i}^{a}\\}_{i=1}^{n_{a}}$ sampled from the augmented classes
distribution $P_{a}(x)$, and Let $y_{i}\in\\{p,n,a\\}$ denotes the class
label, $\mathcal{Y}=\\{p,n,a\\}$ denotes the label space of PUAC. Let
$p_{p}(x)=p(x|y=p)$, $p_{n}(x)=p(x|y=n)$, $p_{a}(x)=p(x|y=a)$ denote the
class-conditional densities for positive, unlabeled and augmented classes
distributions respectively, $\widetilde{D}=D_{p}\cup D_{u}\cup D_{a}$ denote
the aggregated dataset, $P(x,y)$ denotes the distribution of $\widetilde{D}$,
$\pi_{p}=p(y=p)$, $\pi_{n}=p(y=n)$ and $\pi_{a}=p(y=a)$ denote the class prior
probabilities for aggregated dataset.

Data generation process  Let
$\theta_{p}^{p}$,$\theta_{p}^{n}$,$\theta_{p}^{a}$, $\theta_{u}^{p}$,
$\theta_{u}^{n}$,$\theta_{u}^{a}$, $\theta_{a}^{p}$, $\theta_{a}^{n}$ and
$\theta_{a}^{a}$ be class priors for positive, unlabeled and augmented classes
distributions. The data collected for PUAC is assumed to be i.i.d sample from
the marginal densities as follows:

$\begin{array}[]{l}{P_{{p}}(x)}=\theta_{p}^{p}{p_{p}(x)}+\theta_{p}^{n}{p_{n}(x)}+\theta_{p}^{a}{p_{a}(x)},\vspace{1ex}\\\
{P_{u}(x)}=\theta_{u}^{p}{p_{p}(x)}+\theta_{u}^{n}{p_{n}(x)}+\theta_{u}^{a}{p_{a}(x)},\vspace{1ex}\\\
{P_{a}(x)}=\theta_{a}^{p}{p_{p}(x)}+\theta_{a}^{n}{p_{n}(x)}+\theta_{a}^{a}{p_{a}(x)}\end{array}$
(1)

where $\theta_{p}^{p}=1$, $\theta_{p}^{n}=\theta_{p}^{a}=0$,
$\theta_{u}^{p}+\theta_{u}^{n}=1$, $\theta_{u}^{a}=0$ and
$\theta_{a}^{p}+\theta_{a}^{n}+\theta_{a}^{a}=1$. In the PUAC problem setting,
the number of free class priors is three, which could be estimated by various
methods that is similar to the traditional PU learning.

Data generation process states that the distribution of PUAC data can be
regarded as a mixture of positive, negative and augmented classes with some
class priors. It is noteworthy that it does not matter that augmented classes
distribution equals to the testing distribution. It means that collecting data
from augmented classes distribution is easier than from the testing
distribution, which is not a stable distribution during the collecting phase
in the non-stationary environments. In the experiments, empirical results
confirm the robustness for class distribution shifting in the testing
distribution.

###  2.2 Risk Rewrite

In supervised positive, negative and augmented classes classification, let
$f:\mathcal{X}\to\mathcal{Y}$ denotes the decision function, i.e.,$f$ may be
any multi-class classifier. Let
$\mathnormal{l}:\mathcal{Y}\times\mathcal{Y}\to\mathbb{R}$ be the loss
function, and given class priors $\pi_{p}=p(y=p)$, $\pi_{n}=p(y=n)$ and
$\pi_{a}=p(y=a)$, the risk of $f$ is formulated as follows:

$R_{\mathnormal{l}}(f)={\mathbb{E}_{(x,y)\sim
p(x,y)}}[\mathnormal{l}(f(x),y)]=\sum\limits_{i=p,n,a}{{\pi_{i}}{\mathbb{E}_{x\sim{p_{i}}}}[\mathnormal{l}(f(x),i)]}$
(2)

where $p(x,y)$ denotes the distribution of supervised dataset, $p_{i}$ denotes
the $i^{th}$ class-conditional density, i.e., $p_{i}(x)=P(x|y=i)$.

In the PUAC problem, since the negative and augmented classes examples are
unavailable, we cannot estimate
${\mathbb{E}_{x\sim{p_{n}}}}[\mathnormal{l}(f(x),n)]$ and
${\mathbb{E}_{x\sim{p_{a}}}}[\mathnormal{l}(f(x),a)]$, which means that Eq.2
is unable to calculate for PUAC directly. Thus, we rewrite the risk by using
unlabeled and augmented classes distribution to replace the supervised multi-
class risk $R_{l}(f)$. The definition of risk rewrite for PUAC is shown as
follows.

Definition 1. The risk $R_{\mathnormal{l}}(f)$ is rewritable for PUAC setting
on the basis of three marginal densities $P_{{p}}$, $P_{{u}}$ and $P_{{a}}$,
and if and only if there exist constants
$\alpha_{p}$,$\alpha_{n}$,$\alpha_{a}$,$\beta_{p}$,$\beta_{n}$,$\beta_{a}$,$\gamma_{p}$,$\gamma_{n}$
and $\gamma_{a}$, such that for any $f$ it hold that

$R_{\mathnormal{l}}(f)={\mathbb{E}_{P_{p}}}[\mathnormal{\widetilde{l}_{p}}(f(x))]+{\mathbb{E}_{P_{u}}}[\mathnormal{\widetilde{l}_{u}}(f(x))]+{\mathbb{E}_{P_{a}}}[\mathnormal{\widetilde{l}_{a}}(f(x))]$
(3)

where
$\widetilde{l}_{p}(f(x))=\alpha_{p}l(f({{x}}),p)+\alpha_{n}l(f({{x}}),n)+\alpha_{a}l(f({{x}}),a)$,
$\widetilde{l}_{u}(f(x))=\beta_{p}l(f({{x}}),p)+\beta_{n}l(f({\text{x}}),n)+\beta_{a}l(f({\text{x}}),a)$
and
$\widetilde{l}_{a}(f(x))=\gamma_{p}l(f({\text{x}}),p)+\gamma_{n}l(f({\text{x}}),n)+\gamma_{a}l(f({\text{x}}),a)$
are the corrected loss functions.

If the risk is rewritable for PUAC setting, the PUAC risk can be expressed as
expectation over $p_{p}(x)$, $p_{n}(x)$ and $p_{a}(x)$ separately, which
builds a bridge to achieve an unbiased risk estimator.

##  3 Learning from PUAC

In this section, we first prove the risk is rewritable for PUAC setting. Then
we describe the practical implementation for learning from positive and
unlabeled learning with augmented classes. In this paper, all the proofs can
be found in Appendix.

###  3.1  Risk Rewrite for PUAC

Now, we attempt to express the supervised positive, negative and augmented
classes risk $R_{l}(f)$ on the basis of the three marginal densities given in
Section 2.1. According to the Definition 1, if we find the constants
$\alpha_{p}$,$\alpha_{n}$,$\alpha_{a}$,$\beta_{p}$,$\beta_{n}$,$\beta_{a}$,$\gamma_{p}$,$\gamma_{n}$
and $\gamma_{a}$, we could rewrite the PUAC risk. Fortunately, we show that
those constants can be obtained by utilizing class priors. An answer to find
constants is given by the following Theorem 2.

Theorem 2. Fix class priors $\theta_{p}^{p}$, $\theta_{u}^{p}$,
$\theta_{u}^{n}$, $\theta_{a}^{p}$, $\theta_{a}^{n}$ and $\theta_{a}^{a}$,
then the supervised multi-classification $R_{l}(f)$ is rewritable, by letting
$\alpha_{p}=\frac{\pi_{p}}{\theta_{p}^{p}}$,$\,\,\alpha_{n}=-\frac{\theta_{u}^{p}\pi_{u}}{\theta_{p}^{p}\theta_{u}^{n}}\,$,$\,\,\alpha_{a}=\frac{\theta_{a}^{n}\pi_{a}-\theta_{a}^{p}\theta_{u}^{n}\pi_{a}}{\theta_{p}^{p}\theta_{u}^{n}\theta_{a}^{a}}$,$\,\,\beta_{p}=0$,$\,\,\beta_{n}=\frac{\pi_{n}}{\theta_{u}^{n}}$,$\,\,\beta_{a}=-\frac{\theta_{a}^{n}\pi_{a}}{\theta_{u}^{n}\theta_{a}^{a}}$,$\,\,\gamma_{p}=0$,$\,\,\gamma_{n}=0$
and $\,\,\gamma_{a}=\frac{\pi_{a}}{\theta_{a}^{a}}$.

As the results of above theorem, we can express the PUAC risk using data
collected from positive, unlabeled and augmented classes distribution. Let
$\widetilde{l}_{p}(f(x))$, $\widetilde{l}_{u}(f(x))$ and
$\widetilde{l}_{a}(f(x))$ be

$\displaystyle\widetilde{l}_{p}(f(x))=\frac{\pi_{p}}{\theta_{p}^{p}}l(f({\text{x}}),p)-\frac{\theta_{u}^{p}\pi_{u}}{\theta_{p}^{p}\theta_{u}^{n}}l(f({\text{x}}),n)+\frac{\theta_{a}^{n}\pi_{a}-\theta_{a}^{p}\theta_{u}^{n}\pi_{a}}{\theta_{p}^{p}\theta_{u}^{n}\theta_{a}^{a}}l(f({\text{x}}),a)$
(4)
$\displaystyle\widetilde{l}_{u}(f(x))=\frac{\pi_{n}}{\theta_{u}^{n}}l(f({{x}}),n)-\frac{\theta_{a}^{n}\pi_{a}}{\theta_{u}^{n}\theta_{a}^{a}}l(f({{x}}),a)$
(5)
$\displaystyle\widetilde{l}_{a}(f(x))=\frac{\pi_{a}}{\theta_{a}^{a}}l(f({{x}}),a)$
(6)

Proposition 3. The classification risk can be rewritten equivalently as

$\begin{split}R_{\mathnormal{PUAC,l}}(f)&={{\mathbb{E}_{x\sim{P_{p}}}}[\widetilde{l}_{p}(f(x))]+{\mathbb{E}_{x\sim{P_{u}}}}[\widetilde{l}_{u}(f(x))]+{\mathbb{E}_{x\sim{P_{a}}}}[\widetilde{l}_{a}(f(x))]}\\\
&=\mathbb{E}_{x\sim{P_{p}}}\bigg{[}\frac{\pi_{p}}{\theta_{p}^{p}}l(f({{x}}),p)-\frac{\theta_{u}^{p}\pi_{u}}{\theta_{p}^{p}\theta_{u}^{n}}l(f({{x}}),n)+\frac{\theta_{a}^{n}\pi_{a}-\theta_{a}^{p}\theta_{u}^{n}\pi_{a}}{\theta_{p}^{p}\theta_{u}^{n}\theta_{a}^{a}}l(f({{x}}),a)\bigg{]}\\\
&\;\;\;\;+{\mathbb{E}_{x\sim{P_{u}}}}\big{[}\frac{\pi_{n}}{\theta_{u}^{n}}l(f({{x}}),n)-\frac{\theta_{a}^{n}\pi_{a}}{\theta_{u}^{n}\theta_{a}^{a}}l(f({{x}}),a)\big{]}+{\mathbb{E}_{x\sim{P_{a}}}}[\frac{\pi_{a}}{\theta_{a}^{a}}l(f({{x}}),a)]\end{split}$
(7)

The Proposition 3 naturally leads to an unbiased estimator for PUAC. In the
empirical minimization framework, Eq.7 is replaced with their empirical as
follows:

$\widehat{R}_{\mathnormal{PUAC,l}}(f)={\frac{1}{{{n_{p}}}}\sum\limits_{i=1}^{{n_{p}}}}\widetilde{l}_{p}(f(x))+\frac{1}{{n_{u}}}\sum\limits_{i=1}^{n_{u}}\widetilde{l}_{u}(f(x))+\frac{1}{{n_{a}}}\sum\limits_{i=1}^{n_{a}}\widetilde{l}_{a}(f(x))$
(8)

where the $n_{p}$, $n_{u}$ and $n_{a}$ denotes the number of examples
collected form positive, unlabeled and augmented classes distributions
respectively. In the rest of the paper, the process of obtaining the empirical
risk minimizer of Eq.8, i.e., ${\widehat{f}_{PUAC}}=\arg{\min_{f\in
F}}{R_{PUAC,{{l}}}}(f)$ is named as PUAC learning. In this paper, we propose a
ERM-based PUAC learning, and consequently, ${\widehat{f}_{PUAC}}$ can be
obtained by optimizing the Eq.8.

Special case Consider the Eq.8 by specifying class priors. It is obvious that
PUAC problem reduces to Positive and Unlabeled learning, if $\theta_{u}^{n}=0$
and $\theta_{a}^{n}=0$ and the augmented classes data is seen as unlabeled
examples. Then, we can train the classifier by using the positive and
unlabeled learning. Besides, PUAC problem reduces to the standard Positive and
Unlabeled learning, if $\theta_{a}^{a}=0$.

###  3.2 Practical Implementation

In this section, we investigate the practical implementation when the deep
model is employed as classifier for PUAC.

Loss function for PUAC problem We investigate appropriate choice of the loss
function $l$. Typically, the discrete loss is computationally hard, such as,
$\mathds{1}[y\neq p]$, where $\mathds{1}(\bullet)$ denotes the indicator
function. Thus, surrogate losses for multi-class learning with consistency
propertiesZhang (2004); Narasimhan et al. (2015) are used to replace discrete
losses. Some practical examples of common multi-class loss function could be
considered which satisfy the consistency proven in Zhang (2004).

One group of the loss functions $\mathnormal{l}$ is the zero-one loss, i.e.,
$\mathnormal{l}_{0-1}(f(x),y)=\mathds{1}[f(x)\neq y]$. Then, Eq.7 is known as
the classification error. In the multi-classification, the One-Versus-Rest
(OVR) strategy with margin loss $\mathnormal{l_{mar}}$ has the guarantee that
$R_{\mathnormal{l_{mar}}}(f_{p},f_{n},f_{a})$ and
$R_{l_{0-1}}(f_{p},f_{n},f_{a})$ have the same minimizer over all decision
functions Zhang (2004). The $\mathnormal{l_{mar}}$ is formulated as,

$l_{mar}(f_{p}(x),f_{n}(x),f_{a}(x),y)=\phi({f_{y}}(x))+\sum\limits_{\begin{subarray}{l}i=p,n,a\\\
i\neq y\end{subarray}}{\phi(-{f_{i}}(x))}$ (9)

where $f_{i}$ denotes the classifier for $i^{th}$ class,
$\phi(z):\mathbb{R}\to[0,\infty)$ is a binary convex surrogate loss, and
$z=yf(x)$ denotes the margin. Many margin loss functions satisfy consistency
properties for multi-class problem, such as square loss $\phi(z)=(1-z)^{2}$.
Then, According to the OVR strategy with margin loss, the loss
$\widetilde{l}_{p}(f_{p}(x),f_{n}(x),f_{a}(x)$ is formulated as

$\begin{split}\widetilde{l}_{p}(f_{p}(x),f_{n}(x),f_{a}(x))=&\frac{\pi_{p}}{\theta_{p}^{p}}[\phi({f_{p}}(x))+\phi(-{f_{n}}(x))+\phi(-{f_{a}}(x))]\\\
&-\frac{\theta_{u}^{p}\pi_{u}}{\theta_{p}^{p}\theta_{u}^{n}}[\phi(-{f_{p}}(x))+\phi({f_{n}}(x))+\phi(-{f_{a}}(x))]\\\
&+\frac{\theta_{a}^{n}\pi_{a}-\theta_{a}^{p}\theta_{u}^{n}\pi_{a}}{\theta_{p}^{p}\theta_{u}^{n}\theta_{a}^{a}}[\phi(-{f_{p}}(x))+\phi(-{f_{n}}(x))+\phi({f_{a}}(x))]\end{split}$
(10)

The similar formulation can be obtained for loss $\widetilde{l}_{u}(f(x))$ and
$\widetilde{l}_{a}(f(x))$. After obtaining the binary classifier $f_{i}$, we
can construct the multi-class predictor as $f:X\to Y$ with
$f(x)=\arg{\max_{k\in\\{p,n,a\\}}}{f_{k}}(x)$.

Another group of loss for multi-class problem is ordinal regression
lossFinocchiaro et al. (2019); Ramaswamy and Agarwal (2016); Pedregosa et al.
(2017), e.g. using absolute distance:

${l_{ord}}(f_{o}(x),y)=\left|{f_{o}(x)-y}\right|\;\;\;\;\;\;\;\forall
f_{o}(x),y\in\\{p,n,a\\}$ (11)

where label $p=1$, $n=2$ and $a=3$, $f_{o}(x)$ denotes the multi-class
classifier. Many surrogate losses satisfy consistency properties for ordinal
regression loss in multi-class learning, such as absolute surrogate loss.
Compared to zero-one surrogate loss with three dimension classifier, the
prediction dimension of absolute surrogate is one, which can be employed to
develop computationally efficient methodsFinocchiaro et al. (2019). Let
$\phi_{y}(f_{o}(x))$ denotes the absolute surrogate loss, the multi-class loss
$l_{abs}$ can be formulated as

$l_{abs}(f_{o}(x),y)=\phi_{y}(f_{o}(x))=\left|{f_{o}(x)-y}\right|\;\;\;\;\;\;\;\forall
y\in\\{p,n,a\\},f_{o}(x)\in R$ (12)

We now give the risk minimization of Eq.7 as follows

$\begin{split}R_{\mathnormal{PUAC,l_{abs}}}(f_{o})&=\mathbb{E}_{x\sim{P_{p}}}\bigg{[}\frac{\pi_{p}}{\theta_{p}^{p}}|f_{o}(x)-p|-\frac{\theta_{u}^{p}\pi_{u}}{\theta_{p}^{p}\theta_{u}^{n}}|f_{o}(x)-n|+\frac{\theta_{a}^{n}\pi_{a}-\theta_{a}^{p}\theta_{u}^{n}\pi_{a}}{\theta_{p}^{p}\theta_{u}^{n}\theta_{a}^{a}}|f_{o}(x)-a|\bigg{]}\\\
&\;\;\;\;+{\mathbb{E}_{x\sim{P_{u}}}}\big{[}\frac{\pi_{n}}{\theta_{u}^{n}}|f_{o}(x)-n|-\frac{\theta_{a}^{n}\pi_{a}}{\theta_{u}^{n}\theta_{a}^{a}}|f_{o}(x)-a|\big{]}+{\mathbb{E}_{x\sim{P_{a}}}}[\frac{\pi_{a}}{\theta_{a}^{a}}|f_{o}(x)-a|]\end{split}$
(13)

Given the empirical loss of Eq.13, we can obtain the $\widehat{f}_{PUAC,o}$ by
powerful stochastic optimization algorithm for deep models. After obtain the
multi-class classifier, we can construct the predictor as $f:X\to Y$ with
$f(x)=\arg{\min_{k\in\\{p,n,a\\}}}|{\widehat{f}_{PUAC,o}}(x)-k|$.

Class Prior Estimation It is noteworthy that the optimization of the proposed
model requires estimating class priors, when the class priors were assumed to
be unknown. In this section, we propose a class prior estimation algorithm
from PU and augmented classes datasets.

Since we have samples collected from positive and unlabeled distributions, we
can estimate $\theta_{u}^{p}$ and $\theta_{a}^{p}$ by mixture proportion
estimation methodsRamaswamy et al. (2016) easily. For estimating
$\theta_{a}^{n}$, we employ the kernel embedding proposed by, which use
reproducing kernel Hilbert distance to estimate the mixture proportion. If
$\theta_{u}^{n}$ and $\theta_{u}^{p}$ are estimated, class-conditional
distribution can be expressed as
${p_{n}}(x)=\frac{{{P_{u}}(x)-\theta_{u}^{p}{P_{p}}(x)}}{{\theta_{u}^{n}}}$.
Then, the kernel mapping distribution can be obtained from positive and
unlabeled datasets. Since we have some examples collected from augmented
classes distribution, the kernel mean distance can be computed between
$p_{n}(x)$ and augmented classes distribution $P_{a}$ from those datasets.
Thus, class prior $\theta_{a}^{n}$ can be estimated for PUAC problem.

##  4 Theoretical Analysis

In this section, we first study consistency property of proposed PUAC risk
$R_{\mathnormal{PUAC,l_{mar}}}$. Then, we provide the theoretical analysis of
error bound.

Now, we show the Bayes classifiers for OVR strategy with zero-one loss
$l_{0-1}$, and show that the PUAC risk $R_{\mathnormal{PUAC,l_{mar}}}$ is
consistent with the supervised multi-class risk $R_{\mathnormal{l_{0-1}}}$.

Definition 4. (Bayes classifiers for zero-one loss). Let $f^{*}:X\to Y$ be a
classifier, $P(y=c\left|x\right.)$ denotes the conditional density. Then, the
optimal classifier is obtained by minimizing the classification error, which
often was referred to the Bayes classifiers for zero-one loss given by

${f^{*}}(x)=\arg{\max_{c\in\\{p,n,a\\}}}P(y=c\left|x\right.)$ (14)

The following theorem states that by minimizing the risk of
$R_{\mathnormal{PUAC,l_{mar}}}$ , we can obtain the Bayes classifier for zero-
one loss.

Theorem 5. Let $f_{p}$, $f_{p}$ and $f_{a}$ denotes binary classifiers for
positive, negative and augmented classes, and
$f(x)=\arg{\max_{k\in\\{p,n,a\\}}}{f_{k}}(x)$, the surrogate loss $\phi(z)$ is
convex, bounded below, differentiable, and $\phi(z)<\phi(-z)$ when $z>0$, then
for any $\epsilon_{1}>0$, there exists $\epsilon_{2}>0$ such that

$R_{PUAC,{l_{mar}}}({f_{p}},{f_{n}},{f_{a}})\leqslant
R_{PUAC,{l_{mar}}}^{*}+{\varepsilon_{2}}\Longrightarrow{R_{0-1}}(f)\leqslant{R_{0-1}^{*}}+{\varepsilon_{1}}$
(15)

where
$R_{PUAC,{l_{mar}}}^{*}=min_{{f_{p}},{f_{n}},{f_{a}}}R_{PUAC,{l_{mar}}}({f_{p}},{f_{n}},{f_{a}})$
and $R_{0-1}^{*}=min_{f}R_{0-1}(f)=R_{0-1}(f^{*})$ denotes the Bayes error for
multi-class distribution.

Theorem 5 analysis the consistency property for proposed method, which means
that we can obtain classifier achieving Bayes rule. According to Definition 4,
it is obvious that the Bayes classifiers will achieve optimal classification
error under class probabilities shift as usual in the testing distribution. By
minimizing the PUAC risk $R_{PUAC,{l_{mar}}}$, we can get well-behaved
classifiers the same as learning with supervised multi-class data.

Now, we analyze the generalization error bounds for the proposed approach
implemented by deep neural networks using OVR strategy. Let
$\mathbf{f}=({f_{p}},{f_{n}},{f_{a}})$ denotes classification vector function
in the deep network hypothesis set $\mathcal{F}$. Assume there is
$C_{\phi}>0$, such that $su{p_{z}}\phi(z)\leqslant C_{\phi}/3$,
$K_{a}=max(\frac{\pi_{p}}{\theta_{p}^{p}},\frac{\theta_{u}^{p}\pi_{u}}{\theta_{p}^{p}\theta_{u}^{n}},|\frac{\theta_{a}^{n}\pi_{a}-\theta_{a}^{p}\theta_{u}^{n}\pi_{a}}{\theta_{p}^{p}\theta_{u}^{n}\theta_{a}^{a}}|)$,
$K_{u}=max(\frac{\pi_{n}}{\theta_{u}^{n}},\frac{\theta_{a}^{n}\pi_{a}}{\theta_{u}^{n}\theta_{a}^{a}})$
and $K_{a}=\frac{\pi_{a}}{\theta_{a}^{a}}$. Let $L_{\phi}$ be the Lipschitz
constant of $\phi$, we can establish the following lemma.

Lemma 6. For any $\delta>0$, with the probability at least $1-\delta/2$,

${\sup_{\mathbf{f}\in\mathcal{F}}}\left|{{R_{p}}(\mathbf{f})-{\widehat{R}_{p}}(\mathbf{f})}\right|\leqslant
6{K_{p}}{L_{\phi}}{\mathfrak{R}_{{n_{p}}}}(\mathcal{F})+3{K_{p}}{C_{\phi}}\sqrt{\frac{{\ln(4/\delta)}}{{2{n_{p}}}}}$
${\sup_{\mathbf{f}\in\mathcal{F}}}\left|{{R_{u}}(\mathbf{f})-{\widehat{R}_{u}}(\mathbf{f})}\right|\leqslant
4{K_{u}}{L_{\phi}}{\mathfrak{R}_{{n_{u}}}}(\mathcal{F})+2{K_{u}}{C_{\phi}}\sqrt{\frac{{\ln(4/\delta)}}{{2{n_{u}}}}}$
${\sup_{\mathbf{f}\in\mathcal{F}}}\left|{{R_{a}}(\mathbf{f})-{\widehat{R}_{a}}(\mathbf{f})}\right|\leqslant
2{K_{a}}{L_{\phi}}{\mathfrak{R}_{{n_{a}}}}(\mathcal{F})+{K_{a}}{C_{\phi}}\sqrt{\frac{{\ln(4/\delta)}}{{2{n_{a}}}}}$

where
$R_{p}(\mathbf{f})=\mathbb{E}_{x\sim{P_{p}}}[\widetilde{l}_{p}(\mathbf{f}(x))]$,
$R_{u}(\mathbf{f})=\mathbb{E}_{x\sim{P_{u}}}[\widetilde{l}_{u}(\mathbf{f}(x))]$
and
$R_{a}(\mathbf{f})=\mathbb{E}_{x\sim{P_{a}}}[\widetilde{l}_{a}(\mathbf{f}(x))]$,
${\widehat{R}_{p}}(\mathbf{f})$, ${\widehat{R}_{u}}(\mathbf{f})$ and
${\widehat{R}_{a}}(\mathbf{f})$ denote the empirical risk estimator to
$R_{p}(\mathbf{f})$, $R_{u}(\mathbf{f})$ and $R_{a}(\mathbf{f})$ respectively,
$\mathfrak{R}_{{n_{p}}}(\mathcal{F})$, $\mathfrak{R}_{{n_{u}}}(\mathcal{F})$
and $\mathfrak{R}_{{n_{a}}}(\mathcal{F})$ are the Rademacher complexitiesMohri
et al. (2018) of $\mathcal{F}$ for the sampling of size $n_{p}$ from
$P_{p}(x)$, the sampling of size $n_{u}$ from $P_{u}(x)$ and the sampling of
size $n_{a}$ from $P_{a}(x)$.

Based on the Lemma 6, we can obtain the estimation error bound as follows.

Theorem 7. For any $\delta>0$, with the probability at least $1-\delta/2$,

$\begin{split}R_{l_{mar}}({\hat{\mathbf{f}}_{puac})}-\mathop{\rm{min}}_{{\mathbf{f}}\in\mathcal{F}}R_{l_{mar}}(\mathbf{f})\leqslant&12{K_{p}}{L_{\phi}}{\mathfrak{R}_{{n_{p}}}}(\mathcal{F})+8{K_{u}}{L_{\phi}}{\mathfrak{R}_{{n_{u}}}}(\mathcal{F})+4{K_{a}}{L_{\phi}}{\mathfrak{R}_{{n_{a}}}}(\mathcal{F})\\\
&+3{K_{p}}{C_{\phi}}\sqrt{\frac{{\ln(4/\delta)}}{{2{n_{p}}}}}+2{K_{u}}{C_{\phi}}\sqrt{\frac{{\ln(4/\delta)}}{{2{n_{u}}}}}+{K_{a}}{C_{\phi}}\sqrt{\frac{{\ln(4/\delta)}}{{2{n_{a}}}}}\end{split}$

where $\hat{\mathbf{f}}_{puac}$ is trained by minimizing the PUAC risk
$R_{PUAC,{l_{mar}}}$

Lemma 6 and Theorem 7 show that, with a growing number of positive, unlabeled
and augmented classes data, the estimation error of the trained classifiers
decreases, which means that the proposed method is consistent. When deep
network hypothesis set $\mathcal{F}$ is fixed and
$\mathfrak{R}_{{n}}(\mathcal{F})\leqslant C_{\mathcal{F}}/\sqrt{n}$, we have
$\mathfrak{R}_{{n_{p}}}(\mathcal{F})=\mathcal{O}(1/\sqrt{n_{p}})$,
$\mathfrak{R}_{{n_{u}}}(\mathcal{F})=\mathcal{O}(1/\sqrt{n_{u}})$ and
$\mathfrak{R}_{{n_{a}}}(\mathcal{F})=\mathcal{O}(1/\sqrt{n_{a}})$, then

${n_{p}},{n_{u}},{n_{a}}\to\infty\Longrightarrow
R_{l_{mar}}({\hat{\mathbf{f}}_{puac})}-\mathop{\rm{min}}_{{\mathbf{f}}\in\mathcal{F}}R_{l_{mar}}(\mathbf{f})\to
0$

Lemma 6 and Theorem 7 theoretically justify the effective of proposed method
in exploiting augmented classes data.

##  5 Experiments

In this section, we experimentally analyze the proposed approach from three
aspects: 1) Classification accuracy for each class and identification accuracy
for augmented classes comparing with state-of-the-art methods; 2) Robustness
for inaccurate training class priors; 3) Accuracy for class distribution
shifting in the testing distribution.

###  5.1 Performance Comparison

Datasets: In this section, we conduct experiments on five datasets, i.e.,
MNIST, Fashion-MNIST, Kuzushiji-MNIST, SVNH and CIFAR-10. The MNIST, Fashion-
MNIST and Kuzushiji-MNIST datasets consists of 70000 examples which originally
have 10 classes. The SVHN dataset consists of 73257 examples with 10 classes.
The CIFAR-10 dataset consists of 60000 examples associated with a label form
10 classes. We constructed the positive, unlabeled and augmented classes
datasets as follows: we first select three classes form original datasets as
positive, negative and augmented classes datasets respectively. Then, we
randomly select examples from positive dataset as positive class dataset,
examples form positive and negative datasets as unlabeled dataset, and
examples from positive , negative and augmented classes as augmented dataset.
In the constructed procedure, each example is selected into only one dataset.
For performance comparison, we use the original testing datasets as the
testing datasets.

Table 1: Classification accuracy of each algorithm on benchmark datasets, with
varying classes and the number of examples. P = 1, N=3, A=5 means that classes
${1},3,5$ are taken as positive, negative, and augmented classes respectively.
$\\#$ PU and $\\#$ AC denote the number of training examples in PU and
augmented classes datasets. We report the mean and standard deviation of
results over 5 trials. The best method is shown in bold (under 5$\%$ t-test).

Dataset | P, N, A |  $\\#$PU |  $\\#$AC | UPU | NNPU | MPU | AREA | UPUAC
---|---|---|---|---|---|---|---|---
| 1,3,5 | 7591 | 10703 | 37.77$\pm$4.71 | 40.38$\pm$1.42 | 73.65$\pm$0.58 | 57.27$\pm$4.22 | 98.90$\pm$0.24
| 1,3,5 | 11320 | 6680 | 46.41$\pm$8.67 | 41.64$\pm$5.15 | 90.39$\pm$1.57 | 86.39$\pm$0.33 | 98.70$\pm$0.11
MNIST | 5,3,1 | 10625 | 7669 | 42.90$\pm$1.84 | 42.33$\pm$2.98 | 90.14$\pm$1.12 | 83.16$\pm$6.09 | 99.47$\pm$0.08
| 3,5,1&2 | 10102 | 14150 | 25.24$\pm$2.06 | 27.20$\pm$2.30 | 89.66$\pm$0.33 | 77.86$\pm$1.68 | 99.42$\pm$0.13
| 9,8,7&6 | 10313 | 13670 | 39.13$\pm$3.78 | 42.04$\pm$1.96 | 91.10$\pm$0.41 | 72.68$\pm$5.37 | 98.39$\pm$0.21
| 1,3,5 | 10335 | 7665 | 39.98$\pm$3.71 | 34.14$\pm$11.76 | 94.51$\pm$0.10 | 87.70$\pm$0.81 | 98.60$\pm$0.06
Fashion | 2,5,8 | 8650 | 9350 | 33.46$\pm$1.30 | 37.00$\pm$6.90 | 89.43$\pm$0.47 | 65.01$\pm$3.00 | 98.80$\pm$0.08
| 9,8,7 | 8658 | 9342 | 29.22$\pm$1.05 | 27.03$\pm$3.05 | 86.45$\pm$1.37 | 65.22$\pm$1.52 | 97.30$\pm$0.11
| 1,3,5 | 8674 | 9326 | 33.74$\pm$1.05 | 31.52$\pm$0.51 | 74.72$\pm$0.55 | 49.49$\pm$1.27 | 94.31$\pm$0.52
Kuzushiji | 2,4,6 | 10320 | 7680 | 31.44$\pm$3.33 | 31.05$\pm$2.56 | 77.36$\pm$0.32 | 53.97$\pm$0.19 | 93.87$\pm$0.50
| 9,8,6 | 9987 | 8013 | 36.12$\pm$6.92 | 35.18$\pm$3.66 | 81.34$\pm$0.71 | 57.90$\pm$1.47 | 96.15$\pm$0.33

Table 2: Identification accuracy of augmented classes on benchmark datasets,
with varying classes and the number of examples. We report the mean and
standard deviation of results over 5 trials. P = 1, N=3, A=5 means that
classes ${1},3,5$ are taken as positive, negative, and augmented classes
respectively. $\\#$ train AC denotes the number of training examples in
augmented classes datasets. The best method is shown in bold (under 5$\%$
t-test).

Dataset |  | MNIST |  |  | Fashion |  |  | Kuzushiji |
---|---|---|---|---|---|---|---|---|---
P, N, A | 5, 3, 1 | 1, 3, 5 | 9, 8, 7 | 1, 3, 5 | 2, 5, 8 | 9, 8, 7 | 1, 3, 5 | 3, 5, 1 | 9, 8, 7
$\\#$train AC | 9955 | 10703 | 11173 | 7665 | 9350 | 9342 | 9326 | 8304 | 8013
MPU | 84.68$\pm$1.33 | 93.55$\pm$1.52 | 75.73$\pm$6.93 | 91.90$\pm$1.34 | 94.42$\pm$0.33 | 82.72$\pm$3.37 | 75.42$\pm$5.31 | 68.78$\pm$4.97 | 72.78$\pm$2.52
AREA | 59.05$\pm$1.79 | 72.77$\pm$4.50 | 54.01$\pm$3.83 | 88.22$\pm$2.27 | 52.98$\pm$10.21 | 49.62$\pm$9.59 | 44.62$\pm$8.49 | 39.70$\pm$10.12 | 47.70$\pm$5.36
UPUAC | 98.22$\pm$ 0.48 | 98.89$\pm$0.15 | 97.28$\pm$0.55 | 96.98$\pm$0.31 | 98.86$\pm$0.49 | 97.74$\pm$1.00 | 96.36$\pm$1.00 | 97.14$\pm$0.27 | 92.92$\pm$1.10

Common Setup: We conduct experiments using OVR strategy implemented by margin
square loss $\phi(z)=(1-z)^{2}$. As a classifier, we also used neural network
with 4 convolutional layers and 2 fully-connected layers for CIFAR-10, neural
network with 3 convolutional layers and 2 fully-connected layers for SVHN and
2 convolutional layers and 2 fully-connected layers for all the MNIST
datasets. We used AdadeltaZeiler (2012) for optimization and squared loss for
experiments.

There are four contenders, consisting of binary PU learning approaches and
multi-class PU learning approaches. We also report the classification accuracy
on each class and identification accuracy for augmented classes. The details
about the compared methods are described below.

Binary PU Learning: UPUdu Plessis et al. (2015) and NNPUKiryo et al. (2017)
are state-of-the-art binary PU learning approaches. We use the logistic loss
for UPU and the sigmoid loss for NNPU. To compare with two binary PU learning
approaches fairly, we merge the unlabeled and augmented classes datasets as
new unlabeled dataset for binary classifier. Then for the testing phase, the
predicted class of classifier is given as $argmax\\{f_{p},f_{n}\\}$ and the
accuracy of classifier is calculated the same as multi-classes classification.

Multi-class PU Learning: MPUXu et al. (2017) and AREAShu et al. (2020) are
state-of-the-art multi-class PU learning approaches. For comparing with two
approaches fairly, the positive and unlabeled datasets were treads as two
positive classes datasets and augmented classes dataset was treats as
unlabeled dataset. In the testing phase, the predicted class is given as
$argmax\\{f_{p},f_{n},f_{a}\\}$.

Figure 2: Illustrations classification accuracy of two datasets in experiments
with various positive (P), negative (N) and augmented classes (A), datasets.
Table 3: Classification accuracy for inaccurate training class priors on MNIST
dataset. P = 1, N=3, A=5 means that classes ${1},3,5$ are taken as positive,
negative, and augmented classes respectively. $\\#$ PU and $\\#$ AC denote the
number of training examples in PU and augmented classes datasets. We report
mean and standard deviation over 3 trials for varying degrees of inaccuracies.

Dataset | P, N, A |  $\\#$PU |  $\\#$AC |  $\eta_{u}^{p}=0.8$ $\eta_{a}^{p}=0.8$ $\eta_{a}^{n}=0.8$ |  $\eta_{u}^{p}=0.9$ $\eta_{a}^{p}=0.9$ $\eta_{a}^{n}=0.9$ |  $\eta_{u}^{p}=1$ $\eta_{a}^{p}=1$ $\eta_{a}^{n}=1$ |  $\eta_{u}^{p}=1.1$ $\eta_{a}^{p}=1.1$ $\eta_{a}^{n}=1.1$ |  $\eta_{u}^{p}=1.2$ $\eta_{a}^{p}=1.2$ $\eta_{a}^{n}=1.2$
---|---|---|---|---|---|---|---|---
| 1,3,5 | 10752 | 7542 | 99.44$\pm$0.07 | 99.23$\pm$0.17 | 99.20$\pm$0.13 | 99.30$\pm$0.14 | 99.35$\pm$0.08
MNIST | 5,3,1 | 9659 | 8635 | 99.16$\pm$0.04 | 99.27$\pm$0.11 | 99.29$\pm$0.08 | 99.22$\pm$0.10 | 99.25$\pm$0.04
| 2,4,6 | 9771 | 7947 | 99.09$\pm$0.05 | 99.06$\pm$0.16 | 99.25$\pm$0.07 | 99.00$\pm$0.30 | 99.17$\pm$0.14

Dataset | P, N, A |  $\\#$PU |  $\\#$AC |  $\eta_{u}^{p}=0.8$ $\eta_{a}^{p}=1$ $\eta_{a}^{n}=1.2$ |  $\eta_{u}^{p}=0.9$ $\eta_{a}^{p}=1$ $\eta_{a}^{n}=1.1$ |  $\eta_{u}^{p}=1$ $\eta_{a}^{p}=0.8$ $\eta_{a}^{n}=1.2$ |  $\eta_{u}^{p}=1$ $\eta_{a}^{p}=1.1$ $\eta_{a}^{n}=0.9$ |  $\eta_{u}^{p}=1.2$ $\eta_{a}^{p}=0.8$ $\eta_{a}^{n}=1$
---|---|---|---|---|---|---|---|---
| 1,3,5 | 10752 | 7542 | 99.20$\pm$0.20 | 99.26$\pm$0.24 | 99.38$\pm$0.19 | 99.24$\pm$0.06 | 99.30$\pm$0.15
MNIST | 5,3,1 | 9659 | 8635 | 99.27$\pm$0.07 | 99.30$\pm$0.14 | 99.20$\pm$0.07 | 99.26$\pm$0.02 | 99.17$\pm$0.17
| 2,4,6 | 9771 | 7947 | 98.94$\pm$0.38 | 99.13$\pm$0.14 | 99.08$\pm$0.19 | 99.13$\pm$0.20 | 99.10$\pm$0.14

Table.1 reports the classification accuracy of each algorithm on three
datasets. It is obvious that the proposed method achieves the best result of
all the binary PU learning and multi-class PU learning methods. Note that the
performance of multi-class PU learning approaches MPU and AREA is better than
binary PU learning approaches, since the positive and augmented classes can be
learned for multi-class classifiers. The noise only exists in negative
examples for learning multi-class classifier. The similar trends are shown on
identification accuracy. Table.2 reports the identification accuracy as well
as the standard deviation of each algorithm. Fig.2 reports the experimental
results on SVNH and CIFAR-10. We observer that the classification accuracy of
MPU and AREA is very similar. Moreover, UPUAC is significantly better than
multi-class positive and unlabeled learning methods.

Table 4: Classification accuracy of proposed method for class distribution
shifting on MNIST dataset. P = 3, N=4, A=5 means that classes ${3},4,5$ are
taken as positive, negative, and augmented classes respectively. $\\#$ PU and
$\\#$ AC denote the number of training examples in PU and augmented classes
datasets. We report mean and standard deviation over 3 trials for varying
degrees of shift.

Dataset | P, N, A |  $\\#$PU |  $\\#$AC |  $\eta_{p}=0.8$ $\eta_{n}=1$ $\eta_{a}=1.2$ |  $\eta_{p}=0.9$ $\eta_{n}=1$ $\eta_{a}=1.1$ |  $\eta_{p}=1$ $\eta_{n}=1$ $\eta_{a}=1$ |  $\eta_{p}=1.2$ $\eta_{n}=1$ $\eta_{a}=0.8$ |  $\eta_{p}=1.1$ $\eta_{n}=1$ $\eta_{a}=0.9$
---|---|---|---|---|---|---|---|---
| 7,8,9 | 10109 | 7956 | 98.16$\pm$0.33 | 97.80$\pm$0.12 | 98.10$\pm$0.20 | 98.02$\pm$0.25 | 98.10$\pm$0.48
MNIST | 9,8,7 | 9826 | 8239 | 98.95$\pm$0.11 | 98.86$\pm$0.16 | 98.95$\pm$0.15 | 98.63$\pm$0.05 | 98.67$\pm$0.25
| 3,4,5 | 9955 | 7439 | 99.56$\pm$0.12 | 99.70$\pm$0.09 | 99.54$\pm$0.25 | 99.56$\pm$0.20 | 99.61$\pm$0.08

Dataset | P, N, A |  $\\#$PU |  $\\#$AC |  $\eta_{p}=0.8$ $\eta_{n}=1.1$ $\eta_{a}=1.2$ |  $\eta_{p}=0.9$ $\eta_{n}=1.1$ $\eta_{a}=1.1$ |  $\eta_{p}=0.9$ $\eta_{n}=0.8$ $\eta_{a}=1.2$ |  $\eta_{p}=0.9$ $\eta_{n}=1.2$ $\eta_{a}=0.9$ |  $\eta_{p}=1.2$ $\eta_{n}=1.2$ $\eta_{a}=0.9$
---|---|---|---|---|---|---|---|---
| 7,8,9 | 10109 | 7956 | 97.79$\pm$0.33 | 97.73$\pm$0.25 | 97.77$\pm$0.17 | 97.87$\pm$0.03 | 97.83$\pm$0.50
MNIST | 9,8,7 | 9826 | 8239 | 98.87$\pm$0.17 | 98.80$\pm$0.19 | 98.82$\pm$0.17 | 98.79$\pm$0.20 | 98.66$\pm$0.07
| 3,4,5 | 9955 | 7439 | 99.63$\pm$0.07 | 99.73$\pm$0.03 | 99.76$\pm$0.03 | 99.68$\pm$0.11 | 99.45$\pm$0.03

###  5.2 Robustness for Inaccurate Training Class Priors

In above section, we have assumed that the class priors are accessible at the
time of training. Here, we study the robustness for inaccurate training class
priors, which can be estimated with mixture proportion estimation. Without
loss of generality, we conduct the experiments on varying degrees of
inaccuracies for class priors in the training phase. Let $\eta_{u}^{p}$,
$\eta_{a}^{p}$ and $\eta_{a}^{n}$ be real number around 1,
$\vartheta_{u}^{p}=\eta_{u}^{p}\theta_{u}^{p}$,
$\vartheta_{a}^{p}=\eta_{a}^{p}\theta_{a}^{p}$ and
$\vartheta_{a}^{n}=\eta_{a}^{n}\theta_{a}^{n}$ be perturbed class priors. In
this section, we draw data by using $\theta_{u}^{p}$, $\theta_{a}^{p}$ and
$\theta_{a}^{n}$ but train models by using $\vartheta_{u}^{p}$
,$\vartheta_{a}^{p}$ and $\vartheta_{a}^{n}$ instead. Table.3 shows the
classification accuracy, where training class priors varies from 0.8 to 1.2
under ground-truth priors. We observer that the proposed model is robust to
inaccurate $\theta_{u}^{p}$, $\theta_{a}^{p}$ and $\theta_{a}^{n}$ in mild
environment, which prevents the performance degeneration of proposed approach
from misspecified mixture proportions.

###  5.3 Handling Class Probabilities Shift

In this section, we investigate class distribution shift in the testing data.
Without loss of generality, we conduct the experiments on varying degrees of
class distribution shift in the testing phase. Using the similar setting in
section 5.2, let $\eta_{p}$, $\eta_{n}$ and $\eta_{a}$ be real number around
1, $\pi^{\prime}_{p}=\eta_{p}\pi_{p}$, $\pi^{\prime}_{n}=\eta_{n}\pi_{n}$ and
$\pi^{\prime}_{a}=\eta_{a}\pi_{a}$ be the testing class probabilities, and we
report experimental results on MNIST by training model using $\pi_{p}$,
$\pi_{n}$ and $\pi_{a}$ but testing model using $\pi^{\prime}_{p}$,
$\pi^{\prime}_{n}$ and $\pi^{\prime}_{a}$ instead. Table.4 reports the
performance for handling class distribution shifting in terms of
classification accuracy. The results prove that our approach can also overcome
the class distribution shift problem in the open environment.

##  6 Conclusion

In this paper, we investigate the problem of learning from positive and
unlabeled data with unobserved augmented classes by exploiting augmented
classes data. We propose an unbiased risk estimator for positive and unlabeled
learning with augmented classes. Besides, we provide a theoretical analysis of
estimation error bound, which certainly guarantees the estimator converges to
the optimal solution. Experiments demonstrated the effectiveness of proposed
methods. In the future, we will study multi-positive and unlabeled data with
unobserved augmented classes, which is common in real-world applications.
Besides, an interesting future issue is to investigate the advanced method for
PUAC without augmented classes data.

## References

  * Bao et al. [2018] Han Bao, Gang Niu, and Masashi Sugiyama.  Classification from pairwise similarity and unlabeled data.  In _International Conference on Machine Learning, ICML, Stockholmsmässan, Stockholm, Sweden_ , volume 80, pages 461–470, 2018.
  * Bekker and Davis [2020] Jessa Bekker and Jesse Davis.  Learning from positive and unlabeled data: a survey.  _Mach. Learn._ , 109(4):719–760, 2020.
  * Bekker et al. [2019] Jessa Bekker, Pieter Robberechts, and Jesse Davis.  Beyond the selected completely at random assumption for learning from positive and unlabeled data.  In _Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD, Würzburg, Germany_ , volume 11907, pages 71–85, 2019.
  * Da et al. [2014] Qing Da, Yang Yu, and Zhi-Hua Zhou.  Learning with augmented class by exploiting unlabeled data.  In _Proceedings of Conference on Artificial Intelligence, AAAI Québec City, Québec, Canada_ , pages 1760–1766, 2014.
  * du Plessis et al. [2014] Marthinus Christoffel du Plessis, Gang Niu, and Masashi Sugiyama.  Analysis of learning from positive and unlabeled data.  In _Annual Conference on Neural Information Processing Systems, NeurIPS, Montreal, Quebec, Canada_ , pages 703–711, 2014.
  * du Plessis et al. [2015] Marthinus Christoffel du Plessis, Gang Niu, and Masashi Sugiyama.  Convex formulation for learning from positive and unlabeled data.  In _International Conference on Machine Learning, ICML, Lille, France_ , volume 37, pages 1386–1394, 2015.
  * du Plessis et al. [2017] Marthinus Christoffel du Plessis, Gang Niu, and Masashi Sugiyama.  Class-prior estimation for learning from positive and unlabeled data.  _Mach. Learn._ , 106(4):463–492, 2017.
  * Finocchiaro et al. [2019] Jessica Finocchiaro, Rafael M. Frongillo, and Bo Waggoner.  An embedding framework for consistent polyhedral surrogates.  In _Annual Conference on Neural Information Processing Systems, NeurIPS, Vancouver, BC, Canada_ , pages 10780–10790, 2019.
  * Guo et al. [2020a] Lan-Zhe Guo, Zhenyu Zhang, Yuan Jiang, Yu-Feng Li, and Zhi-Hua Zhou.  Safe deep semi-supervised learning for unseen-class unlabeled data.  In _International Conference on Machine Learning, ICML, Virtual Event_ , volume 119, pages 3897–3906, 2020a.
  * Guo et al. [2020b] Tianyu Guo, Chang Xu, Jiajun Huang, Yunhe Wang, Boxin Shi, Chao Xu, and Dacheng Tao.  On positive-unlabeled classification in GAN.  In _IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR, Seattle, WA, USA_ , pages 8382–8390, 2020b.
  * Ishida et al. [2018] Takashi Ishida, Gang Niu, and Masashi Sugiyama.  Binary classification from positive-confidence data.  In _Annual Conference on Neural Information Processing Systems, NeurIPS, Montréal, Canada_ , pages 5921–5932, 2018.
  * Kato et al. [2019] Masahiro Kato, Takeshi Teshima, and Junya Honda.  Learning from positive and unlabeled data with a selection bias.  In _International Conference on Learning Representations, ICLR, New Orleans, LA, USA_ , 2019.
  * Kiryo et al. [2017] Ryuichi Kiryo, Gang Niu, Marthinus Christoffel du Plessis, and Masashi Sugiyama.  Positive-unlabeled learning with non-negative risk estimator.  In _Annual Conference on Neural Information Processing Systems, NeurIPS, Long Beach, CA, USA_ , pages 1675–1685, 2017.
  * Li and Liu [2003] Xiaoli Li and Bing Liu.  Learning to classify texts using positive and unlabeled data.  In Georg Gottlob and Toby Walsh, editors, _Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI, Acapulco, Mexico_ , pages 587–594. Morgan Kaufmann, 2003.
  * Lu et al. [2019] Nan Lu, Gang Niu, Aditya Krishna Menon, and Masashi Sugiyama.  On the minimal supervision for training any binary classifier from only unlabeled data.  In _International Conference on Learning Representations, ICLR, New Orleans, LA, USA_ , 2019.
  * Mohri et al. [2018] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar.  _Foundations of machine learning_.  2018\.
  * Mordelet and Vert [2014] Fantine Mordelet and Jean-Philippe Vert.  A bagging SVM to learn from positive and unlabeled examples.  _Pattern Recognit. Lett._ , 37:201–209, 2014.
  * Narasimhan et al. [2015] Harikrishna Narasimhan, Harish G. Ramaswamy, Aadirupa Saha, and Shivani Agarwal.  Consistent multiclass algorithms for complex performance measures.  In _International Conference on Machine Learning, ICML, Lille, France_ , volume 37, pages 2398–2407, 2015.
  * Niu et al. [2016] Gang Niu, Marthinus Christoffel du Plessis, Tomoya Sakai, Yao Ma, and Masashi Sugiyama.  Theoretical comparisons of positive-unlabeled learning against positive-negative learning.  In _Annual Conference on Neural Information Processing Systems, NeurIPS, Barcelona, Spain_ , pages 1199–1207, 2016.
  * Pedregosa et al. [2017] Fabian Pedregosa, Francis R. Bach, and Alexandre Gramfort.  On the consistency of ordinal regression methods.  _J. Mach. Learn. Res._ , 18:55:1–55:35, 2017.
  * Pham et al. [2015] Anh T. Pham, Raviv Raich, Xiaoli Z. Fern, and Jesús Pérez Arriaga.  Multi-instance multi-label learning in the presence of novel class instances.  In _International Conference on Machine Learning, ICML, Lille, France_ , volume 37, pages 2427–2435, 2015.
  * Ramaswamy and Agarwal [2016] Harish G. Ramaswamy and Shivani Agarwal.  Convex calibration dimension for multiclass loss matrices.  _J. Mach. Learn. Res._ , 17:14:1–14:45, 2016.
  * Ramaswamy et al. [2016] Harish G. Ramaswamy, Clayton Scott, and Ambuj Tewari.  Mixture proportion estimation via kernel embeddings of distributions.  In _International Conference on Machine Learning, ICML, New York City, NY, USA_ , volume 48, pages 2052–2060, 2016.
  * Sakai and Shimizu [2019] Tomoya Sakai and Nobuyuki Shimizu.  Covariate shift adaptation on learning from positive and unlabeled data.  In _The Thirty-Third Conference on Artificial Intelligence, AAAI, Honolulu, Hawaii, USA_ , pages 4838–4845, 2019.
  * Sansone et al. [2019] Emanuele Sansone, Francesco G. B. De Natale, and Zhi-Hua Zhou.  Efficient training for positive unlabeled learning.  _IEEE Trans. Pattern Anal. Mach. Intell._ , 41(11):2584–2598, 2019.
  * Shimada et al. [2021] Takuya Shimada, Han Bao, Issei Sato, and Masashi Sugiyama.  Classification from pairwise similarities/dissimilarities and unlabeled data via empirical risk minimization.  _Neural Comput._ , 33(5):1234–1268, 2021.
  * Shu et al. [2020] Senlin Shu, Zhuoyi Lin, Yan Yan, and Li Li.  Learning from multi-class positive and unlabeled data.  In _International Conference on Data Mining, ICDM, Sorrento, Italy_ , pages 1256–1261. IEEE, 2020.
  * Wei et al. [2021] Xiu-Shen Wei, Han-Jia Ye, Xin Mu, Jianxin Wu, Chunhua Shen, and Zhi-Hua Zhou.  Multi-instance learning with emerging novel class.  _IEEE Trans. Knowl. Data Eng._ , 33(5):2109–2120, 2021.
  * Xu et al. [2017] Yixing Xu, Chang Xu, Chao Xu, and Dacheng Tao.  Multi-positive and unlabeled learning.  In _Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI, Melbourne, Australia_ , pages 3182–3188. ijcai.org, 2017.
  * Zeiler [2012] Matthew D. Zeiler.  ADADELTA: an adaptive learning rate method.  abs/1212.5701, 2012.
  * Zhang [2004] Tong Zhang.  Statistical analysis of some multi-category large margin classification methods.  _J. Mach. Learn. Res._ , 5:1225–1251, 2004.
  * Zhang et al. [2020] Yu-Jie Zhang, Peng Zhao, Lanjihong Ma, and Zhi-Hua Zhou.  An unbiased risk estimator for learning with augmented classes.  In _Annual Conference on Neural Information Processing Systems, NeurIPS, virtual_ , 2020.