Open Category Detection with PAC Guarantees

正文索引 [隐藏]

这篇文章的方法并不新颖,亮点在于对于问题给出了一个 PAC 证明,给出了样本数量和问题设定参数之间的关系,这一点在新类检测相关文章汇总是不多见的。

Motivation & Problem

给定一个包含已知类的数据集 $S_0$ 与混合已知类与新类的无标记数据集 $S_m$,在测试集上新类检测的查全率达到 $1-q$ ,同时尽可能提升查准率,且我们知道 $S_m$ 中已知类与新类的估计混合比例 $\alpha$ 或上限 $\alpha’$。

这里 $S_0$ 是从已知类别数据分布 $D_0$ 中采样得到的,$S_m$ 从 $D_0$ 与新类数据分布 $D_a$ 按照 $1-\alpha:\alpha$ 混合得到的 $D_m$ 中采样得到的,测试数据集的分布没有特殊要求。

感觉这个问题的研究动机还是蛮自然的,毕竟新类重要的问题还是非常多的,比如说:我们想要发现没有见过的物种、识别诈骗中没有见过的操作…… 这类问题通常要有一个有保证的查全率,在查全率达到要求的时候再尽可能的提升查准率。

Methods

文章检测新类的方法比较简单,直接将检测新类转化为异常检测问题。使用异常检测的工具,测试数据的每一个样本给定一个异常评分,那么问题就在于如何设定一个合适的阈值 $\tau_q$ 使得查全率有保证。

解决这个问题就可以直接在 $S_m$ 上进行估计,因为 $S_m$ 包含已知比例的已知类与新类,我们可以通过它估计 $\tau_q$。

假设数据集关于异常值的 CDF 分别为 $F_0, F_m$,那么由 $D_m = (1 – \alpha) D_0 + \alpha D_a$,可得知 $F_a = \frac{F_m – (1-\alpha)F_0 }{\alpha}$。由于 $F_0, F_m$ 均可以通过数据集进行估计得 $\hat{F_0}, \hat{F_m}$,所以我们也能得到估计的 $\hat{F_a}$。然后据此,计算出满足 $1-q$ 查全率的 $\hat{\tau_q}$ 即可。

对于有限的样本,文章同样估计出了查全率性能保证的界。对于 $\forall \epsilon \in[0, 1-q] $ 与 $\delta\in[0,1]$,如果:
$$
n>\frac{1}{2}ln\frac{2}{1-\sqrt{1-\delta}}(\frac{1}{\epsilon})^2(\frac{2-\alpha}{\alpha})^2
$$
满足至少有 $1-\delta$ 的概率,算法能够返回一个 $\hat{\tau_q}$ 保证查全率达到 $1-q-\epsilon$。

当我们不知道准确的混合比例 $\alpha$ 的时候,如果估计出 $\alpha$ 的上界且异常检测器满足某种条件(数据越混乱异常评分越大)依旧可以得到这个界。

Result

文章有了一定的理论保证,做实验只需要验证理论的结论即可,具体实验见论文。

Conclusion

文章的问题设定有一定的意义,即我们经常面对一个查全率很重要的场景,第一强调查全率与其理论保证。文章的方法算是比较简单的,理论结果是否 Amazing 还有待进一步了解。

一点思考就是文章虽然也使用了无标记数据,但是和半监督利用方式完全不同,本文方法仅利用无标记数据估计 $\hat{\tau_q}$,而没有引入半监督假设在构建异常检测器的时候对无标记数据进行利用,感觉这里是有一定的利用空间的。

说实话,文章的应用常见也并非非常多,因为我们需要实现采样到存在新类的无标记数据并且估计比例 $\alpha$,这对于需要持续运行在动态环境中的算法是非常困难的,只能不断暴力重新采样当前无标记数据、估计 $\alpha$ 并建立模型。

是否有对于查准率要求十分高的场景呢?我觉得也是有的,应该常见于 FP 对于用户困扰的场景。比如:

  • 新类检测 + 主动学习的时候,我们要尽可能降低查询用户的次数,这个时候一个 FP 将浪费很多机会。
    • 终端设备通过用户操作习惯检查是否为新用户,向用户查询当前是否为新用户
    • 文件 / 照片自动分类,查询是否需要新建分类