本文主要考虑的是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. mushrooms、 shuttle、 pageblocks、 usps、 connect-4 、 spambase
    • 首先用logistic回归估计了$P(y = +1 | x)$的概率，然后用其20倍的概率作为selection bias对正样本进行采样，然后用之前提到的最小化PU risk和LSIF方法分别对 $\hat{r}$ 进行估计，从而得到分类器。
    • 文中使用不同的$\pi$和未标记数据集大小进行实验，发现其算法都好于之前的方法，但两种$r$的估计方法在不同的数据集中有好有坏。
  2. MNIST、CIFAR-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