本文主要考虑的是PU learning,也就是在只有正类数据和无标记数据的情况下,对数据进行二分类。在case-control
情境下(也就是two samples问题),之前大部分研究基于都基于selected completely at random
的假设,但本文argue这种假设不符合实际,因此对该假设进行了放松:如果$P(o = +1| x)$越高,则$P(y = +1| x)$也越高,反之亦然,这种性质被称为invariance of order
。
使用Bayes公式推导可以得到,密度比也符合这种偏序关系。因此,论文认为,虽然我们很难得到$P(y=+1|x)$具体的值,但通过估计密度比,能得到样本间是正类的概率偏序关系,这样通过一个合理的阈值作为分类器即可区分正负类。
作者通过两种方法来估计密度比:一种是根据之前研究定义的classification risk
推广到有based
的classification risk函数,然后根据公式$\hat{r} = \frac{\hat f}{\pi}$计算得到;另一种方法是直接用uLSIF
进行估计。得到密度比$r$之后,根据先验信息$\pi$,对数据进行遍历即可得到$\theta_\pi$阈值,通过该阈值可以实现在未标记数据上将正负样本进行区分。
最后,作者在几个常见的数据集上进行了改造以符合PU learning的假设,同时使用了一个real-world数据集,使用论文提到的两个方法估计$\hat{r}$,然后可以得到阈值$\theta_\pi$,进而得到二分类器。最后还验证了在未知先验$\pi$的情况下,其算法的robust较好。
Intuition
- cast-control scenario
- P 是从正类中采样的,U 是从整个样本空间采样的,这两者相互独立。这个假设符合现实中的认识,因为如果有标记的样本都是正例,那么一定是人为忽略或是丢弃了负类样本。换句话说,unlabel data 中既包含正样本,也包含负样本,称为为 two samples 问题,即有 P 和 U 两个采样集。
- selected completely at random (SCAR)
- 对于
cast-control
的问题,常见的假设是:正类被标记的采样集和未标记的采样集是独立同分布的。 - 作者 argue 这种假设在现实问题中很多时候不成立,例如在异常检测中,异常的更容易被选中;在人脸识别中,用户更倾向于提供清晰的照片(labeled),而未标记的数据更可能非常不清晰。
- 对于
- select bias
- 因此在现实中,作者认为$P(x|y = +1,o = 0) \ne P(x|y = +1,o = +1)$,不能简单的通过Bayes公式推断得到$P(y = +1 | x)$的概率。
- 虽然不能直接得到$P(y = +1 | x)$的值,但根据之前的假设,如果数据更容易被标记,则它是正样本的概率更大,可以得到这样的偏序关系:
- $P(y = +1 | x_i) \le P(y = +1| x_j) \Leftrightarrow P(o = +1 | x_i)\le P(o = +1| x_j)$
- 如果取等号,那么就满足了
SCAR
假设,因此,本文定义的invariance of order
可以看作是SCAR
的推广。
Strategy
作者主要的思路是:
- 使用正类数据和未标记数据,通过最小化
pseduo classification risk
或者LSIF
对密度比$r(x)$进行估计 - 通过先验$\pi$和$r(x)$,认为test data中的数据分布与先验应该相同,估计阈值$\theta_\pi$
- 通过简单的符号函数即可构造一个二分类器将未标记数据进行区分
基本概念
- density ratio
- 我们用密度比的概念来衡量数据之间的差异性,这种差异可以用来区分正负样本。
- 定义为: $r(x) = \frac{P(x|y = +1,o = +1)}{P(x)}$,作者在这里称为打分函数
- 这里可以理解为从两个数据集中进行抽样的概率密度,如果相差越大(即密度比越大),则越能区分该数据
- 使用Bayes定理和
invariance of order
假设,可以得到:- $P(y = +1 | x_i) \le P(y = +1| x_j) \Leftrightarrow r(x_i)\le r(x_j)$
- 这里给我们的启发是:虽然不能直接得到样本属于正类的概率,但通过打分函数可以捕捉到这种偏序关系。因此,我们如果能对$r$进行估计,设置一个较好的阈值,结合我们先验的$\pi$,就可以用来区分正负样本了。
- $\theta_\pi$的性质
- 我们用阈值将样本分开并逼近先验$\pi$,很自然的问题是,选择这个阈值对于我们分类效果的影响如何?
- 论文附录B证明了:该阈值使得 precision 和recall值一样,因此这个阈值称为BEP,直观的可以认为该点在false positives 和 false negetive找到了很好的平衡。
估计$r(x)$
Minimize PU risk
之前的工作已经得到,在SCAR
假设下,classification risk可以表示为:
$$R_{PU}(f) = \pi E_P[l(f(X),+1)] - \pi E_P[{l(f(X),-1)}] + E_u[l(f(X),-1)]$$
如果数据没有selection bias
,那么直接可以用样本均值代替这里的期望,保证估计出的risk的无偏性。
仿照之前定义的calssification risk,在selection bias
的情境下,我们可以定义完全一样的classification risk,称为psedo classicication risk
,因此我们得到的是关于伪分类风险函数的无偏估计。同时定义loss function为对数损失:
$$R_{PU} (f) = -\pi E_P[\log (f(X))] + \pi E_P[\log(1-f(X))] - E_u[\log(1-f(X))] $$
将期望代替为样本均值,再加上正则项,最小化分类损失函数后得到$\hat{f}$,可以用来估计$\hat{r} = \frac{\hat{f}}{\pi}$
LSIF
论文提供的另外一种估计 $r(x)$ 的方法,使用unconstrained Least-Squares Importance Fitting (uLSIF) 直接对密度比进行估计。其实就是最小化估计值与真实值差的平方的期望。在实际运用中常加入正则项:
$$\hat{r} = \arg \min\limits_{s} [\frac{1}{2}E_u[(s(X))^2] - E_P[s(X)] + R(s) ]$$
估计$\theta_\pi$
根据先验$\pi$以及我们的假设(test data中的正类占比应该不会与先验相差太远),因此我们直接遍历每个样本点的$\hat{r}(x)$,大于阈值的即为正类。因此,用先验得到的正类个数应该和估计的超过阈值的$\hat{r}(x)$相同,即:
$$\pi N = \sum\limits_{i=1}^N 1(\hat{x_i} > \theta_\pi)$$
Experiments
论文主要用了unbiased PU learning
做对比,PUSB
表示用阈值预估的unbiased PU learning,DRSB
表示用uLSIF和阈值估计;nnPU
表示nonnegative PU learning;nnPUSB
表示nonnegative PU learning和阈值估计。。。(这缩写也太多了)
根据估计密度比的不同方法,论文给出了不同的模型:
- 直接使用LSIF对$r$进行估计,其中的$s(x)$使用了线性模型
- $s(x) = \beta^T\Phi(x)$
- 这里的$\Phi(x)$是一系列基函数的向量,这里的基函数使用了高斯核($\phi_l(x) = \exp(-||x-c_l||^2/(2\sigma^2))$
- 使用交叉验证来选择最合适的超参数
- 对于最小化classification risk,其中的$f(x)$使用了sigmoid函数:
- $f(x) = \frac{1}{1+\exp(-\beta^T\Phi(x))}$
- 对于nonegative PU learning,使用了神经网络进行学习,正则化使用了$l_2$范数
论文做了相当数量的实验来证明算法的有效性,可以分为:
mushrooms
、shuttle
、pageblocks
、usps
、connect-4
、spambase
- 首先用logistic回归估计了$P(y = +1 | x)$的概率,然后用其20倍的概率作为
selection bias
对正样本进行采样,然后用之前提到的最小化PU risk和LSIF方法分别对 $\hat{r}$ 进行估计,从而得到分类器。 - 文中使用不同的$\pi$和未标记数据集大小进行实验,发现其算法都好于之前的方法,但两种$r$的估计方法在不同的数据集中有好有坏。
- 首先用logistic回归估计了$P(y = +1 | x)$的概率,然后用其20倍的概率作为
MNIST
、CIFAR-10
- 这些数据集原本是多分类的,作者人为的将其分为了正负样本两类(个人感觉这样强行分类不太具有说服力)
- 同样,使用logistic回归估计了$P(y = +1 | x)$的概率,然后用其10倍的概率作为
selection bias
对正样本进行采样,最后用最小化non-negative risk作为目标函数训练神经网络,估计得到$\hat{r}$,得到分类器后计算recall和precision。
SwissProt
- 这是唯一一个自然存在
bias
的数据集。用词袋模型将文档转为高维向量,使用类似的方法训练神经网络并估计密度比,得到阈值和分类器,计算 recall 和precison。
- 这是唯一一个自然存在
Test for unknown class prior
- 由于该算法的阈值计算依赖于先验 $\pi$,因此我们希望在先验估计得不太准确的情况下,算法的分类效果有较好的robust。使用了
KM2
方法*(待看)*估计了先验概率,并进行了实践,发现其准确率有较大的下降,但在先验偏离越来越远的情况下,其准确率基本趋于稳定。
- 由于该算法的阈值计算依赖于先验 $\pi$,因此我们希望在先验估计得不太准确的情况下,算法的分类效果有较好的robust。使用了