本文主要考虑的是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

作者主要的思路是:

  1. 使用正类数据和未标记数据,通过最小化pseduo classification risk或者LSIF对密度比$r(x)$进行估计
  2. 通过先验$\pi$和$r(x)$,认为test data中的数据分布与先验应该相同,估计阈值$\theta_\pi$
  3. 通过简单的符号函数即可构造一个二分类器将未标记数据进行区分

基本概念

  • 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和阈值估计。。。(这缩写也太多了)

根据估计密度比的不同方法,论文给出了不同的模型:

  1. 直接使用LSIF对$r$进行估计,其中的$s(x)$使用了线性模型
    • $s(x) = \beta^T\Phi(x)$
    • 这里的$\Phi(x)$是一系列基函数的向量,这里的基函数使用了高斯核($\phi_l(x) = \exp(-||x-c_l||^2/(2\sigma^2))$
    • 使用交叉验证来选择最合适的超参数
  2. 对于最小化classification risk,其中的$f(x)$使用了sigmoid函数:
    • $f(x) = \frac{1}{1+\exp(-\beta^T\Phi(x))}$
    • 对于nonegative PU learning,使用了神经网络进行学习,正则化使用了$l_2$范数

论文做了相当数量的实验来证明算法的有效性,可以分为:

  1. mushroomsshuttlepageblocksusps connect-4spambase
    • 首先用logistic回归估计了$P(y = +1 | x)$的概率,然后用其20倍的概率作为selection bias对正样本进行采样,然后用之前提到的最小化PU risk和LSIF方法分别对 $\hat{r}$ 进行估计,从而得到分类器。
    • 文中使用不同的$\pi$和未标记数据集大小进行实验,发现其算法都好于之前的方法,但两种$r$的估计方法在不同的数据集中有好有坏。
  2. MNISTCIFAR-10
    • 这些数据集原本是多分类的,作者人为的将其分为了正负样本两类(个人感觉这样强行分类不太具有说服力)
    • 同样,使用logistic回归估计了$P(y = +1 | x)$的概率,然后用其10倍的概率作为selection bias对正样本进行采样,最后用最小化non-negative risk作为目标函数训练神经网络,估计得到$\hat{r}$,得到分类器后计算recall和precision。
  3. SwissProt
    • 这是唯一一个自然存在bias的数据集。用词袋模型将文档转为高维向量,使用类似的方法训练神经网络并估计密度比,得到阈值和分类器,计算 recall 和precison。
  4. Test for unknown class prior
    • 由于该算法的阈值计算依赖于先验 $\pi$,因此我们希望在先验估计得不太准确的情况下,算法的分类效果有较好的robust。使用了KM2方法*(待看)*估计了先验概率,并进行了实践,发现其准确率有较大的下降,但在先验偏离越来越远的情况下,其准确率基本趋于稳定。

Reference

  1. Open review