PU Learning：只有正样本与未标注数据时怎么办

更新历史

2019.05.11: 完成初稿

背景

PU-learning(Positive and Unlabeled learning)，是一种半监督学习方法，早期工作包括 Liu Bing 等人在 2002 年对文本分类的研究。

在现实生活中，有许多只有正样本和大量未标记样本的例子。这是因为负类样本的一些特点使得获取负样本较为困难。比如：

负类数据不易获取。
负类数据太过多样化。
负类数据动态变化。

举一个形象点的例子：比如在推荐系统里，只有用户点击的正样本，却没有显性负样本，我们不能因为用户没有点击这个样本就认为它是负样本，因为有可能这个样本的位置很偏，导致用户没有点。

众所周知，如果我们的目标样本只有正样本，而存在大量无标注样本情况下，我们一般会有几种解决方式：

将无标注样本作为负样本训练二分类模型，但因为无标注样本中存在大量正样本而导致模型效果差
采用 one-class classification 方法，只学习正类的特征。
采用 PU-learning 中的 two-step strategy 半监督方法，可以有效提升这种情况下的模型效果。即启发式地从未标注样本里找到可靠的负样本，以此训练二分类器，该方法问题是分类效果严重依赖先验知识。

应用范围

Retrieval(检索)
Inlier-based outlier detection. 发现异常值
One-vs-rest classification. 负样本太过分散而不能标注

理论说明

早期的一类方法将问题转换成一个带约束的最优化问题（Constrained Optimization Problem），即算法试图在使得正例数据中的错误率低于1-r的情况下最小化无标注数据中正例数据的数目。

这里按三种常见思路梳理，不代表 PU 学习的全部方法，也不都使用上述优化形式：

两步方法（Two-step Approach）
直接方法（Direct Approach）
Bagging 方法

两步方法

通常，会将第二步的结果返回到第一步并重复上述步骤。即每一轮循环都会找出那些模型判断较可靠的正样本和负样本（仍可能有误标），加入到训练集里，重新预测剩余的未标记样本，直到满足停止条件为止。

参考文献：An Evaluation of Two-Step Techniques for Positive-Unlabeled Learning in Text Classification

两个步骤组成：

从无标注数据集U中发现一些可靠的反例文档集合 RN（Reliable Negative Documents）
利用 Positive、RN 和 U-RN（Q=U-RN，Q也被称为候选集合）来建立分类器，根据 RN 集合中数据的质量和数量的不同，在该步骤中可能会使用某个现有的学习算法一次或循环使用多次。

第一步中所采用的技术：

间谍技术（Spy Technique）：该技术从正例标注集P中选取一些“间谍”文档放到无标注数据集U中去，
- 随机地从 P 中选取一个正例文档集合 S，并把 S 加入到 U 中
- 通过把 P-S 当成是正例集合，U+S 当成是反例集合，在这两个集合上运行朴素贝叶斯算法，得到朴素贝叶斯分类器并用于给 U+S 中的每个文档 d 进行分类，即为每个文档赋予一个概率类别标识 Pr(1|d)，其中 1 代表正例类别。注意，这一步也可以使用 Rocchio分类器
- 利用间谍文档的概率标识来决定哪些文档最有可能是反例。使用一个阈值 t 来确定，U 中那些概率 Pr(1|d) 小于t的文档被认为是最有可能的反例文档，用 RN 表示。
1DNF技术：首先建立一个正例特征集合 PF，其中包括那些在正例集合 P 中出现次数大于在无标注数据 U 中出现次数的单词，得到 U 与 P 中出现的所有单词并得到一个词汇表 V，从 U 中发现可靠反例文档，U 中的某个文档如果不含有 PF 中任何特征的话被认为是一个可靠的反例文档。

第二步中所采用的技术：

在 P 和 RN 上运行一个学习算法（如NB或SVM），集合 U-RN 中的文档不在考虑范围内；迭代地运行某个学习算法直到它收敛或达到某个停止条件。

SVM
- 直接用SVM算法对positive样本和reliable negative样本进行训练
S-EM
- 首先对positive样本标记为1；
- 其次对reliable negative样本标记为-1；
- Q=U-RN；
- 利用EM对于样本进行分类，训练完的分类器再重新预测Q，从Q中抽取RN样本；
- 迭代至无法从Q中抽取RN样本；
PEBL
- 首先对positive样本标记为1；
- 其次对reliable negative样本标记为-1；
- Q=U-RN；
- 利用SVM对于样本进行分类，训练完的分类器再重新预测Q，从Q中抽取RN样本；
- 迭代至无法从Q中抽取RN样本；
Biased SVM

直接方法

直接利用标准分类方法是这样的：将正样本和未标记样本分别看作是positive samples和negative samples, 然后利用这些数据训练一个标准分类器。分类器将为每个物品打一个分数（概率值）。通常正样本分数高于负样本的分数。因此对于那些未标记的物品，分数较高的最有可能为positive。

这种朴素的方法在文献Learning classifiers from only positive and unlabeled data KDD 2008 中有介绍。该论文的核心结果是，在某些基本假设下（虽然对于现实生活目的而言可能稍微不合理),合理利用正例和未贴标签数据进行训练得到的标准分类器应该能够给出与实际正确分数成正比的分数。

PU Bagging

一个更加复杂的方法是bagging的变种：

通过将所有正样本和未标记样本进行随机组合来创建训练集。
利用这个“bootstrap”样本来构建分类器，分别将正样本和未标记样本视为positive和negative。
将分类器应用于不在训练集中的未标记样本 - OOB（“out of bag”）- 并记录其分数。
重复上述三个步骤，最后为每个样本的分数为OOB分数的平均值。

这是一种bootstrap的方法，可以理解为之前我们会想到随机抽取一部分未标记样本U作为负样本来训练，在这里会设置迭代次数T，根据正样本的个数，每次都随机可重复地从U中选取和P数量相同的样本作为负样本N，并打上标签，每次迭代都重复进行取样->建模->预测的过程，最后的预测概率使用T次迭代的平均值作为最终预测分数；分数未经校准不应直接当作概率。

参考文献：A bagging SVM to learn from positive and unlabeled examples ，PRL 2014

参考链接

参考链接中的代码是原笔记使用的历史示例，运行时需核对依赖版本。

标注机制为什么重要

Elkan 与 Noto 的比例校正结果依赖正例被标注的概率不随特征变化，即 SCAR 假设。若 $s=1$ 表示被标注、 $y=1$ 表示真实正例，且 $P(s=1\mid y=1,x)=c$ ，则 $P(s=1\mid x)=cP(y=1\mid x)$ 。推荐场景里的曝光位置往往影响标注机会，不能不检查假设就套用这个结论。

参考：Elkan 与 Noto，Learning Classifiers from Only Positive and Unlabeled Data（2008）。